Objectives

  • Define the maximal margin classifier
  • Define the support vector classifier and discuss the logic of this approach
  • Define support vector machines (SVM) and non-linear decision boundaries
  • Apply SVM classification to example data sets and compare with alternative statistical learning models
library(tidyverse)
library(forcats)
library(broom)
library(modelr)
library(tree)
library(randomForest)
library(stringr)
library(ISLR)
library(titanic)
library(rcfss)
library(pROC)
library(gbm)
library(e1071)
library(grid)
library(gridExtra)

options(digits = 3)
set.seed(1234)
theme_set(theme_minimal())

Support vector machines (SVMs) are a popular statistical learning method for classification tasks.1 SVMs build on several important concepts, that while related are distinct from one another. We will first discuss the logic of these individual components, then demonstrate how to estimate and interpret SVMs, and compare model results using this method to other statistical learning procedures we have discussed so far.

Maximal margin classifier

Hyperplanes

In \(p\)-dimensional space, a hyperplane is a flat subspace of \(p - 1\) dimensions that is affine (does not need to pass through the origin). In two dimensions, a hyperplane is a flat one-dimensional subspace (also known as a line). In three dimensions, a hyper plane is a flat two-dimensional subspace (also known as a plane). In higher dimensions it gets harder to visualize this concept, but the definition still holds true.

In two dimensions, the mathematical equation for a hyperplane is:

\[\beta_0 + \beta_1 X_1 + \beta_2 X_2 = 0\]

Any \(X = (X_1, X_2)^T\) for which this equation holds is a point on the hyperplane (line). This functional form generalizes to \(p\) dimensions quite easily:

\[\beta_0 + \beta_1 X_1 + \beta_2 X_2 + \dots + \beta_p X_p = 0\]

Again, for any point \(X = (X_1, X_2, \dots, X_p)^T\) in \(p\)-dimensional space (i.e. a vector of length \(p\)) that equals 0, then \(X\) lies on the hyperplane.

For \(X\) that does not meet this condition, then the data point lies on either side of the hyperplane:

\[\beta_0 + \beta_1 X_1 + \beta_2 X_2 + \dots + \beta_p X_p > 0\]

\[\beta_0 + \beta_1 X_1 + \beta_2 X_2 + \dots + \beta_p X_p < 0\]

The hyperplane therefore divides the \(p\)-dimensional space into two halves. To determine on which side of the hyperplane an observation lies, we simply calculate the sign of the corresponding hyperplane equation.

sim_hyper <- data_frame(x1 = seq(-1.5, 1.5, length.out = 20),
                        x2 = seq(-1.5, 1.5, length.out = 20)) %>%
  expand(x1, x2) %>%
  mutate(y = 1 + 2 * x1 + 3 * x2,
         group = ifelse(y < 0, -1,
                        ifelse(y > 0, 1, 0)),
         group = factor(group))

sim_hyper_line <- data_frame(x1 = seq(-1.5, 1.5, length.out = 20),
                             x2 = (-1 - 2 * x1) / 3)

ggplot(sim_hyper, aes(x1, x2, color = group)) +
  geom_point() +
  geom_line(data = sim_hyper_line, aes(color = NULL)) +
  labs(title = "Hyperplane in two dimensions") +
  theme(legend.position = "none")

Classification using a separating hyperplane

Let’s represent a hypothetical classification problem as the following: suppose we have an \(n \times p\) data matrix \(\mathbf{X}\) that consists of \(n\) training observations with \(p\) predictors in \(p\)-dimensional space:

\[x_1 = \begin{pmatrix} x_{11} \\ \vdots \\ x_{1p} \end{pmatrix}, \dots, x_n = \begin{pmatrix} x_{n1} \\ \vdots \\ x_{np} \end{pmatrix}\]

These observations fall into one of two classes \(y_1, \dots, y_n \in \{-1, 1 \}\) where \(-1\) and \(1\) represent two separate classes or categories. We also have a test observation \(x^*\) which is a \(p\)-vector of observed predictors \(x^* = (x_1^*, \dots, x_p^*)\). We want to develop a model that classifies the test observation correctly given our knowledge of the training observations. Previously we have used methods such as logistic regression (where the response variable is coded \(\{0, 1 \}\)) and decision trees to perform this task. Now we want to use a hyperplane to separate the training observations into the two possible classes.

A separating hyperplane perfectly separates training observations into their class labels. Observations in the blue class are coded as \(y_i = 1\) those from the red class as \(y_i = -1\). So a separating hyperplane takes on the properties:

\[\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip} > 0, \text{if } y_i = 1\] \[\beta_0 + \beta_1 x_{i1} + \dots + \beta_p x_{ip} < 0, \text{if } y_i = -1\]

sim <- data_frame(x1 = runif(20, -2, 2),
                  x2 = runif(20, -2, 2),
                  y = ifelse(1 + 2 * x1 + 3 * x2 < 0, -1, 1)) %>%
  mutate_each(funs(ifelse(y == 1, . + 1.5, .)), x2) %>%
  mutate(y = factor(y, levels = c(-1, 1))) %>%
  mutate(line1 = (-1 - 2 * x1) / 3,
         line2 = .5 + (-1 - 1.5 * x1) / 3,
         line3 = .25 - .05 * x1)

ggplot(sim, aes(x1)) +
  geom_point(aes(y = x2, color = y)) +
  geom_line(aes(y = line1, color = NULL)) +
  geom_line(aes(y = line2, color = NULL)) +
  geom_line(aes(y = line3, color = NULL)) +
  labs(title = "Examples of separating hyperplanes") +
  theme(legend.position = "none")

If a separating hyperplane exists, then we can classify test observations based on their location relative to the hyperplane:

sim_mod <- svm(y ~ x1 + x2, data = sim, kernel = "linear", cost = 1e05,
               scale = FALSE)
sim_coef <- c(sim_mod$rho, t(sim_mod$coefs) %*% sim_mod$SV)

sim_grid <- data_frame(x1 = seq(-2, 2, length.out = 100),
                  x2 = seq(-2, 3.5, length.out = 100)) %>%
  expand(x1, x2) %>%
  mutate(y = ifelse(-sim_coef[[1]] + sim_coef[[2]] * x1 + sim_coef[[3]] * x2 > 0, -1, 1),
         y = factor(y, levels = c(-1, 1)))

sim_plane <- data_frame(x1 = seq(-2, 2, length.out = 100),
                        x2 = (sim_coef[[1]] - sim_coef[[2]] * x1) / sim_coef[[3]])

ggplot(sim, aes(x1)) +
  geom_point(data = sim_grid, aes(x1, x2, color = y), alpha = .25, size = .25) +
  geom_point(aes(y = x2, color = y)) +
  geom_line(data = sim_plane, aes(x1, x2)) +
  labs(title = "Maximal margin classification") +
  theme(legend.position = "none")

Classifications are based off the sign of \(f(x^*) = \beta_0 + \beta_1 x_1^* + \dots + \beta_p x_p^*\). If \(f(x^*)\) is positive, then we predict the test observation is \(1\). If \(f(x^*)\) is negative, then we predict the test observation is \(-1\). We can also consider the magnitude of \(f(x^*)\): the farther the magnitude is away from zero, then the farther the test observation falls from the hyperplane. We can be more confident of our predictions for observations far from the hyperplane, and less so for observations near the hyperplane (i.e. \(f(x^*)\) close to zero). The classifier resulting from the separating hyperplane \(f(x^*) = \beta_0 + \beta_1 x_1^* + \dots + \beta_p x_p^*\) is a linear decision boundary because the function itself is a linear form.

Maximal margin classifier

As we saw previously, if the data can be perfectly separated by a hyperplane it is likely true that there are multiple potential separating hyperplanes. We need a method for identifying the optimal separating hyperplane. This is known as the maximal margin hyperplane, which is the separating hyperplane that is farthest from the training observations. The margin is the smallest possible (perpendicular) distance between a training observation and the separating hyperplane. This distance is simply \(\hat{f}(x_i)\). The maximal margin hyperplane defines the hyperplane that minimizes the marginal distance across all training observations, and can be used to classify the test observation \(x^*\) based on which side of the hyperplane it lies. This is known as the maximal margin classifier. The expectation is that a classifier with a large margin for the training observations will also have a large margin for the test observations, leading to accurate classifications. As with the other methods we have discussed so far, this is an assumption and it is still possible to overfit the training data using the maximal margin classifier.

sim_pred <- predict(sim_mod, sim, decision.values = TRUE)
sim_dist <- attr(sim_pred, "decision.values")

ggplot(sim, aes(x1)) +
  geom_point(aes(y = x2, color = y)) +
  geom_point(data = sim_grid, aes(x1, x2, color = y), alpha = .1, size = .25) +
  geom_line(data = sim_plane, aes(x1, x2)) +
    geom_line(data = mutate(sim_plane, x2 = x2 - min(abs(sim_dist))),
              aes(x1, x2), linetype = 2) +
    geom_line(data = mutate(sim_plane, x2 = x2 + min(abs(sim_dist))),
              aes(x1, x2), linetype = 2) +
  labs(title = "Maximal margin classification") +
  theme(legend.position = "none")

Two observations are equidistant from the maximal margin hyperplane and lie along the dashed lines indicating the width of the margin. These observations are called the support vectors. They are vectors in \(p\)-dimensional space and “support” the maximal margin hyperplane because if the observations shifted at all in their predictor values \(X\), then the maximal margin hyperplane would shift as well. In fact, the maximal margin hyperplane is defined entirely by the support vectors; changes to the other observations would not effect the separating hyperplane as long as the changed observations do not cross the boundary set by the margin.

Constructing the maximal margin hyperplane

Constructing the maximal margin hyperplane is a (relatively) straight forward affair. Consider a set of \(n\) training observations with some number of real number predictors \(x_1, \dots, x_n \in \mathbb{R}^p\) and associated class labels \(y_1, \dots, y_n \in \{-1, 1\}\). We want to solve the optimization problem:

\[\begin{aligned} & \underset{\beta_0, \beta_1, \dots, \beta_p}{\text{maximize}} & & M \\ & \text{s.t.} & & \sum_{j=1}^p \beta_j^2 = 1, \\ & & & y_i(\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \dots + \beta_p x_{ip}) \geq M \; \forall \; i = 1, \dots, n \\ \end{aligned}\]

This is simpler than it looks. \(y_i(\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \dots + \beta_p x_{ip}) \geq M \; \forall \; i = 1, \dots, n\) requires the maximal margin hyperplane to sort observations on the correct side of the hyperplane with some amount of cushion, provided \(M\) is positive. The requirement \(\sum_{j=1}^p \beta_j^2 = 1\) means that not only are the observations sorted onto the correct sides of the hyperplane, but that the function \(y_i(\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \dots + \beta_p x_{ip})\) defines the perpendicular distance between the observation \(y_i\) and the hyperplane. Therefore \(M\) defines the margin of the hyperplane (i.e. the amount of cushion between the hyperplane and the closest training observations), so we select values for the parameters \(\beta_0, \beta_1, \dots, \beta_p\) to maximize \(M\); that is, obtain the largest amount of cushion possible given the training observations.

Non-separable cases

Unfortunately the maximal margin classifier only works if there exists a separating hyperplane for the data. If the cases cannot be perfectly separated by a hyperplane, then we can never satisfy the conditions of the maximal margin classifier.

data_frame(x1 = runif(20, -2, 2),
           x2 = runif(20, -2, 2),
           y = c(rep(-1, 10), rep(1, 10))) %>%
  mutate(y = factor(y, levels = c(-1, 1))) %>%
  ggplot(aes(x1, x2, color = y)) +
  geom_point() +
  labs(title = "Non-separable data") +
  theme(legend.position = "none")

Support vector classifier

Support vector classifiers relax the requirement of the maximal margin classifier by allowing the separating hyperplane to not perfectly separate the observations; instead, it can make some errors. This is reasonable when:

  1. There exists no perfectly separating hyperplane
  2. A perfectly separating hyperplane is too sensitive to individual training observations, generating potentially very small margins or overfitting the training set.2
# original model
sensitive <- data_frame(x1 = runif(20, -2, 2),
                  x2 = runif(20, -2, 2),
                  y = ifelse(1 + 2 * x1 + 3 * x2 < 0, -1, 1)) %>%
  mutate_each(funs(ifelse(y == 1, . + .5, .)), x2) %>%
  mutate(y = factor(y, levels = c(-1, 1)))

sens_mod <- svm(y ~ x1 + x2, data = sensitive, kernel = "linear",
                cost = 1e05, scale = FALSE)
sens_coef <- c(sens_mod$rho, t(sens_mod$coefs) %*% sens_mod$SV)
sens_plane <- data_frame(x1 = seq(-2, 2, length.out = 100),
                        x2 = (sens_coef[[1]] - sens_coef[[2]] * x1) / sens_coef[[3]])

ggplot(sensitive, aes(x1)) +
  geom_point(aes(y = x2, color = y)) +
  geom_line(data = sens_plane, aes(x1, x2)) +
  labs(title = "Maximal margin classification") +
  theme(legend.position = "none")

# slight tweak
sensitive2 <- data_frame(x1 = with(sensitive, x1[which(x2 == max(x2[y == -1]))]),
                         x2 = with(sensitive, max(x2[y == -1])) + .1,
                         y = factor(1, levels = c(-1, 1))) %>%
  bind_rows(sensitive)

sens2_mod <- svm(y ~ x1 + x2, data = sensitive2, kernel = "linear",
                cost = 1e05, scale = FALSE)
sens2_coef <- c(sens2_mod$rho, t(sens2_mod$coefs) %*% sens2_mod$SV)
sens2_plane <- data_frame(x1 = seq(-2, 2, length.out = 100),
                        x2 = (sens2_coef[[1]] - sens2_coef[[2]] * x1) / sens2_coef[[3]])

ggplot(sensitive2, aes(x1)) +
  geom_point(aes(y = x2, color = y)) +
  geom_line(data = sens2_plane, aes(x1, x2)) +
  geom_line(data = sens_plane, aes(x1, x2), linetype = 2) +
  labs(title = "Maximal margin classification") +
  theme(legend.position = "none")

Instead, we want a separating hyperplane that does not perfectly separate the two classes but provides greater robustness to individual observations and better classification of most training observations. We are willing to sacrifice accuracy on a few observations if the resulting hyperplane performs better across the remaining observations.

This approach is called the support vector classifier. It allows observations to not only exist on the wrong side of the margin (i.e. inside the cushion defined by \(M\)), but also exist on the wrong side of the hyperplane.

The approach is the same as the maximal margin classifier but the optimization problem is slightly different:

\[\begin{aligned} & \underset{\beta_0, \beta_1, \dots, \beta_p, \epsilon_1, \dots, \epsilon_n}{\text{maximize}} & & M \\ & \text{s.t.} & & \sum_{j=1}^p \beta_j^2 = 1, \\ & & & y_i(\beta_0 + \beta_1 x_{i1} + \beta_2 x_{i2} + \dots + \beta_p x_{ip}) \geq M(1 - \epsilon_i), \\ & & & \epsilon_i \geq 0, \sum_{i = 1}^n \epsilon_i \leq C \\ \end{aligned}\]

As in the maximal margin classifier, we attempt to optimize \(M\) to generate the largest possible margin. However now we allow some error \(\epsilon_i\) for each observation so that they can fall on the wrong side of the margin or hyperplane.

  • If \(\epsilon_i = 0\), then the \(i\)th observation falls on the correct side of the margin.
  • If \(\epsilon_i > 0\), then the \(i\)th observation falls on the wrong side of the margin.
  • If \(\epsilon_i > 1\), then the \(i\)th observation falls on the wrong side of the hyperplane.

\(C\) defines precisely how much error we are willing to tolerate in the resulting separating hyperplane. The sum of the errors for all training observations cannot exceed \(C\). Larger values of \(C\) permit more overall error in the separating hyperplane and lead to larger margins, and smaller values of \(C\) tolerate less error and produce smaller margins. If \(C = 0\) then we do not tolerate any error in the separating hyperplane, in which case \(\epsilon_1, \dots, \epsilon_n = 0\) and we estimate the maximal margin classifier (of course this is only possible if the classes are perfectly separable). Once we solve the optimization problem, we generate predictions the same way as for maximal margin classifiers, based on \(f(x^*) = \beta_0 + \beta_1 x_1^* + \dots + \beta_p x_p^*\).

Selecting a value for \(C\) is tricky and generally determined through a cross-validation approach to compare support vector classifiers under different values for \(C\). When \(C\) is small, we generate a model with low-bias (it fits the data well) but high-variance (small changes in the training observations can generate substantial changes in the support vector classifier). If \(C\) is large, we generate a model with more bias but less variance.

The important thing to realize is that the support vector classifier is robust, like the maximal margin classifier, to changes in observations outside of the margin. Observations that lie directly on the margin or inside the margin but on the correct side of the hyperplane are support vectors. The support vector classifier will only change if those observations are adjusted. When \(C\) is large, the number of observations falling inside the margin increases and therefore the number of support vectors also increases.

sim_c <- data_frame(x1 = rnorm(20),
                    x2 = rnorm(20),
                    y = ifelse(2 * x1 + x2 + rnorm(20, 0, .25) < 0, -1, 1)) %>%
  mutate(y = factor(y, levels = c(-1, 1)))

plot_svm <- function(df, cost = 1){
  # estimate model
  sim_mod <- svm(y ~ x1 + x2, data = df, kernel = "linear",
                 cost = cost,
                 scale = FALSE)
  
  # extract separating hyperplane
  sim_coef <- c(sim_mod$rho, t(sim_mod$coefs) %*% sim_mod$SV)
  sim_plane <- data_frame(x1 = seq(min(df$x1), max(df$x1), length.out = 100),
                          x2 = (-sim_coef[[1]] - sim_coef[[2]] * x1) / sim_coef[[3]])
  
  # extract properties to draw margins
  sim_pred <- predict(sim_mod, df, decision.values = TRUE)
  sim_dist <- attr(sim_pred, "decision.values")
  
  ggplot(df, aes(x1)) +
    geom_point(aes(y = x2, color = y)) +
    geom_line(data = sim_plane, aes(x1, x2)) +
    geom_line(data = mutate(sim_plane, x2 = x2 - min(abs(sim_dist))),
              aes(x1, x2), linetype = 2) +
    geom_line(data = mutate(sim_plane, x2 = x2 + min(abs(sim_dist))),
              aes(x1, x2), linetype = 2) +
    labs(subtitle = str_c("Cost = ", cost)) +
    coord_equal(xlim = range(df$x1),
                    ylim = range(df$x2)) +
    theme(legend.position = "none")
}

grid.arrange(grobs = list(plot_svm(sim_c, cost = 1),
                  plot_svm(sim_c, cost = 10),
                  plot_svm(sim_c, cost = 100),
                  plot_svm(sim_c, cost = 200)), ncol = 2)

Support vector machines

Non-linear decision boundaries

So far we have only demonstrated the support vector classifier with a linear decision boundary. But as with linear regression, we also know there are methods of extending the linear framework to account for non-linear relationships. Consider the following relationship:

set.seed(1)
x <- matrix(rnorm(200 * 2), ncol = 2)
x[1:100, ] <- x[1:100, ] + 2
x[101:150, ] <- x[101:150, ] - 2
y <- c(rep(1, 150), rep(2, 50))
sim_nonlm <- data.frame(x = x, y = as.factor(y)) %>%
  as_tibble %>%
  rename(x1 = x.1,
         x2 = x.2)

radial_p <- ggplot(sim_nonlm, aes(x1, x2, color = y)) +
  geom_point() +
  theme(legend.position = "none")
radial_p

A support vector classifier with a linear decision boundary would perform very poorly on this data.

We could go the route we discussed before and relax the linearity assumption by adding quadratic or cubic terms to address the non-linearity. For instance, adding a quadratic term would change the optimization problem to using \(2p\) features:

\[X_1, X_1^2, X_2, X_2^2, \dots, X_p, X_p^2\]

And therefore the optimization problem becomes:

\[\begin{aligned} & \underset{\beta_0, \beta_{11}, \beta_{12}, \dots, \beta_{p1}, \beta_{p2}, \epsilon_1, \dots, \epsilon_n}{\text{maximize}} & & M \\ & \text{s.t.} & & y_i \left( \beta_0 + \sum_{j = 1}^p \beta_{j1} x_{ij} + \sum_{j = 1}^p \beta_{j2} x_{ij}^2 \right) \geq M(1 - \epsilon_i), \\ & & & \epsilon_i \geq 0, \sum_{i = 1}^n \epsilon_i \leq C, \sum_{j = 1}^p \sum_{k = 1}^2 \beta_{jk}^2 = 1 \\ \end{aligned}\]

The problem with this approach is that as you add polynomial terms (or interactions or splines) you increase the feature space used to generate the decision boundary and the separating hyperplane (i.e. the total number of predictors increases). Maximizing this optimization problem is already computationally intensive: if you continue to increase the number of features, computing the support vector classifier becomes much more difficult and inefficient, and may even become impossible.

Support vector machines

The support vector machine is an extension of the support vector classifier that enlarges the feature space by using kernels. Kernels are a computationally efficient method for extending the feature space to accomodate a non-linear decision boundary.

Computing the support vector classifier involves the inner products of the observations, rather than the observations themselves.3 The inner product of two \(r\)-length vectors \(a\) and \(b\) is defined as \(\langle a,b \rangle = \sum_{i = 1}^r a_i b_i\).

(x <- 1:5)
## [1] 1 2 3 4 5
(y <- 1:5)
## [1] 1 2 3 4 5
x %*% y
##      [,1]
## [1,]   55

So the inner product of two observations is:

\[\langle x_i, x_{i'} \rangle = \sum_{j = 1}^p x_{ij} x_{i'j}\]

The linear support vector can be written as:

\[f(x) = \beta_0 + \sum_{i = 1}^n \alpha_i \langle x, x_i \rangle\]

where there are \(n\) parameters \(\alpha_i, i = 1, \dots, n\), one per training observation. To estimate the parameters \(\alpha_1, \dots, \alpha_n, \beta_0\), we just need to calculate the inner products between all pairs of training observations. However for observations which are not also support vectors, \(\alpha_i\) is actually zero. So in fact, we only need to calculate the inner products for support vectors \(\mathbb{S}\) which reduces the complexity of this task:

\[f(x) = \beta_0 + \sum_{i \in \mathbb{S}} \alpha_i \langle x, x_i \rangle\]

Kernels

Now rather than using the actual inner product,

\[\langle x_i, x_{i'} \rangle = \sum_{j = 1}^p x_{ij} x_{i'j}\]

instead we can use a generalization of the inner product following some functional form \(K\) which we will call a kernel:

\[K(x_i, x_{i'})\]

A kernel calculates the similarity of two observations. For example,

\[K(x_i, x_{i'}) = \sum_{j = 1}^p x_{ij} x_{i'j}\]

generates the support vector classifier, also known as the linear kernel. Alternatively, we could use a different kernel function such as:

\[K(x_i, x_{i'}) = (1 + \sum_{j = 1}^p x_{ij} x_{i'j})^d\]

This is called the polynomial kernel of degree \(d\) where \(d\) is some positive integer. This will generate a much more flexible decision boundary, similar to how using a spline in linear regression generates a flexible, non-linear functional form. To use this kernel in a support vector classifier, the functional form becomes:

\[f(x) = \beta_0 + \sum_{i \in \mathbb{S}} \alpha_i K(x,x_i)\]

sim_nonlm <- data_frame(x1 = runif(100, -2, 2),
                  x2 = runif(100, -2, 2),
                  y = ifelse(x1 + x1^2 + x1^3 - x2 < 0 +
                               rnorm(100, 0, 1), -1, 1)) %>%
  mutate(y = factor(y, levels = c(-1, 1)))

ggplot(sim_nonlm, aes(x1, x2, color = y)) +
  geom_point() +
  theme(legend.position = "none")

svm(y ~ x1 + x2, data = sim_nonlm, kernel = "polynomial", scale = FALSE, cost = 1) %>%
  plot(sim_nonlm, x2 ~ x1)

Another choice is the radial kernel:

\[K(x_i, x_{i'}) = \exp(- \gamma \sum_{j=1}^p (x_{ij} - x_{i'j})^2)\]

where \(\gamma\) is some positive constant. Radial kernels work by localizing predictions for test observations based on their Euclidian distance to nearby training observations.

sim_rad_mod <- svm(y ~ x1 + x2, data = sim_nonlm,
                     kernel = "radial", cost = 5, scale = FALSE)

radial_p

plot(sim_rad_mod, sim_nonlm, x2 ~ x1)

Kernels are better to use for support vector machines than other non-linear approachs because they do not enlarge the feature space. That is, you need to compute \(K(x_i, x_{i'})\) for all \(\binom{n}{2}\) distinct pairs \(i, i'\), but \(p\) itself remains the same. You do not need to explicitly enlarge the feature space to accomplish this task. The total number of features/predictors/independent variables in the model remains the same, so you can more easily compute the SVM.

Applying and interpreting SVMs

SVMs are generally used for prediction models. They generate predicted classes for test observations and we can assess confidence in the model and overall model fit using standard metric. However SVMs are not good for conducting inference, since there are no easy methods for interpreting the relative importance and influence of individual predictors on the separating hyperplane. Regression coefficients are generally easy to interpret, and even tree-based methods have visual and statistical interpretations (variable importance plots) of the individual predictors. Generally SVMs are interpreted by assessing overall model fit and error rates, using a combination of cross-validation methods and visuals such as ROC curves.

Titanic

Let’s try this method out on our trusty Titanic dataset, using age and gender to predict survival. First we’ll split our dataset into training and test sets.

titanic <- titanic_train %>%
  as_tibble %>%
  select(-Name, -Ticket, -Cabin, -PassengerId) %>%
  mutate_each(funs(as.factor(.)), Survived, Pclass, Embarked) %>%
  na.omit

titanic_split <- resample_partition(titanic, p = c("test" = .3, "train" = .7))

Our first attempt will use a linear kernel (i.e. support vector classifier) and we’ll use 10-fold cross-validation to determine the optimal cost parameter \(C\).

titanic_tune <- tune(svm, Survived ~ Age + Fare, data = as_tibble(titanic_split$train),
                     kernel = "linear",
                     range = list(cost = c(.001, .01, .1, 1, 5, 10, 100)))
summary(titanic_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost
##     5
## 
## - best performance: 0.364 
## 
## - Detailed performance results:
##    cost error dispersion
## 1 1e-03 0.400     0.0686
## 2 1e-02 0.390     0.0779
## 3 1e-01 0.376     0.0729
## 4 1e+00 0.366     0.0760
## 5 5e+00 0.364     0.0735
## 6 1e+01 0.364     0.0735
## 7 1e+02 0.364     0.0735

\(C = 1\) produces the lower CV error rate, so let’s use that model for estimating model fit using a ROC curve.

titanic_best <- titanic_tune$best.model
summary(titanic_best)
## 
## Call:
## best.tune(method = svm, train.x = Survived ~ Age + Fare, data = as_tibble(titanic_split$train), 
##     ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), 
##     kernel = "linear")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  linear 
##        cost:  5 
##       gamma:  0.5 
## 
## Number of Support Vectors:  372
## 
##  ( 186 186 )
## 
## 
## Number of Classes:  2 
## 
## Levels: 
##  0 1
# get predictions for test set
fitted <- predict(titanic_best, as_tibble(titanic_split$test), decision.values = TRUE) %>%
  attributes

roc_line <- roc(as_tibble(titanic_split$test)$Survived, fitted$decision.values)
plot(roc_line)

auc(roc_line)
## Area under the curve: 0.759

How does this compare to a polynomial kernel SVM?

titanic_poly_tune <- tune(svm, Survived ~ Age + Fare, data = as_tibble(titanic_split$train),
                     kernel = "polynomial",
                     range = list(cost = c(.001, .01, .1, 1, 5, 10, 100)))
summary(titanic_poly_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##   cost
##  0.001
## 
## - best performance: 0.394 
## 
## - Detailed performance results:
##    cost error dispersion
## 1 1e-03 0.394     0.0844
## 2 1e-02 0.398     0.0872
## 3 1e-01 0.396     0.0863
## 4 1e+00 0.398     0.0851
## 5 5e+00 0.396     0.0858
## 6 1e+01 0.398     0.0851
## 7 1e+02 0.396     0.0858
titanic_poly_best <- titanic_poly_tune$best.model
summary(titanic_poly_best)
## 
## Call:
## best.tune(method = svm, train.x = Survived ~ Age + Fare, data = as_tibble(titanic_split$train), 
##     ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), 
##     kernel = "polynomial")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  polynomial 
##        cost:  0.001 
##      degree:  3 
##       gamma:  0.5 
##      coef.0:  0 
## 
## Number of Support Vectors:  397
## 
##  ( 198 199 )
## 
## 
## Number of Classes:  2 
## 
## Levels: 
##  0 1
# get predictions for test set
fitted <- predict(titanic_poly_best, as_tibble(titanic_split$test), decision.values = TRUE) %>%
  attributes

roc_poly <- roc(as_tibble(titanic_split$test)$Survived, fitted$decision.values)
plot(roc_poly)

auc(roc_poly)
## Area under the curve: 0.724

Not quite as good. The optimal cost parameter is smaller (\(.1\)), but the associated CV error rate is higher than the linear kernel and the resulting test AUC is smaller. How does this stack up against the radial kernel?

titanic_rad_tune <- tune(svm, Survived ~ Age + Fare, data = as_tibble(titanic_split$train),
                     kernel = "radial",
                     range = list(cost = c(.001, .01, .1, 1, 5, 10, 100)))
summary(titanic_rad_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost
##   100
## 
## - best performance: 0.326 
## 
## - Detailed performance results:
##    cost error dispersion
## 1 1e-03 0.400     0.0625
## 2 1e-02 0.400     0.0625
## 3 1e-01 0.358     0.0830
## 4 1e+00 0.342     0.0819
## 5 5e+00 0.330     0.0634
## 6 1e+01 0.328     0.0681
## 7 1e+02 0.326     0.0700
titanic_rad_best <- titanic_rad_tune$best.model
summary(titanic_rad_best)
## 
## Call:
## best.tune(method = svm, train.x = Survived ~ Age + Fare, data = as_tibble(titanic_split$train), 
##     ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), 
##     kernel = "radial")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  radial 
##        cost:  100 
##       gamma:  0.5 
## 
## Number of Support Vectors:  334
## 
##  ( 165 169 )
## 
## 
## Number of Classes:  2 
## 
## Levels: 
##  0 1
# get predictions for test set
fitted <- predict(titanic_rad_best, as_tibble(titanic_split$test), decision.values = TRUE) %>%
  attributes

roc_rad <- roc(as_tibble(titanic_split$test)$Survived, fitted$decision.values)
plot(roc_rad)

auc(roc_rad)
## Area under the curve: 0.7

The radial improves upon both the polynomial and the linear SVMs. The CV error rate is lower and the test AUC is higher.

It’s easier to compare if we plot the ROC curves on the same plotting window:

plot(roc_line, print.auc = TRUE, col = "blue")
plot(roc_poly, print.auc = TRUE, col = "red", print.auc.y = .4, add = TRUE)
plot(roc_rad, print.auc = TRUE, col = "orange", print.auc.y = .3, add = TRUE)

Based on our predictions from the test set, the radial SVM performs the best on the AUC, followed by the linear SVM, and worst of all the polynomial SVM.

Voter turnout

Let’s test the SVM method on our voter turnout data. Again, let’s start by splitting the data into training and test sets.4

(mh <- read_csv("data/mental_health.csv") %>%
  mutate_each(funs(as.factor(.)), vote96, black, female, married) %>%
  na.omit)
## # A tibble: 1,165 × 8
##    vote96 mhealth_sum   age  educ  black female married inc10
##    <fctr>       <dbl> <dbl> <dbl> <fctr> <fctr>  <fctr> <dbl>
## 1       1           0    60    12      0      0       0  4.81
## 2       1           1    36    12      0      0       1  8.83
## 3       0           7    21    13      0      0       0  1.74
## 4       0           6    29    13      0      0       0 10.70
## 5       1           1    41    15      1      1       1  8.83
## 6       1           2    48    20      0      0       1  8.83
## 7       0           9    20    12      0      1       0  7.22
## 8       0          12    27    11      0      1       0  1.20
## 9       1           2    28    16      0      0       1  7.22
## 10      1           0    72    14      0      0       1  4.01
## # ... with 1,155 more rows
mh_split <- resample_partition(mh, p = c("test" = .3, "train" = .7))

SVM

Next let’s compare a few different SVM models. Again we’ll use 10-fold CV on the training set to determine the optimal cost parameter.

Linear kernel

mh_lin_tune <- tune(svm, vote96 ~ ., data = as_tibble(mh_split$train),
                    kernel = "linear",
                    range = list(cost = c(.001, .01, .1, 1, 5, 10, 100)))
summary(mh_lin_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost
##     5
## 
## - best performance: 0.294 
## 
## - Detailed performance results:
##    cost error dispersion
## 1 1e-03 0.315     0.0513
## 2 1e-02 0.315     0.0513
## 3 1e-01 0.300     0.0586
## 4 1e+00 0.296     0.0633
## 5 5e+00 0.294     0.0647
## 6 1e+01 0.294     0.0647
## 7 1e+02 0.294     0.0647
mh_lin <- mh_lin_tune$best.model
summary(mh_lin)
## 
## Call:
## best.tune(method = svm, train.x = vote96 ~ ., data = as_tibble(mh_split$train), 
##     ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), 
##     kernel = "linear")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  linear 
##        cost:  5 
##       gamma:  0.125 
## 
## Number of Support Vectors:  513
## 
##  ( 258 255 )
## 
## 
## Number of Classes:  2 
## 
## Levels: 
##  0 1
fitted <- predict(mh_lin, as_tibble(mh_split$test), decision.values = TRUE) %>%
  attributes

roc_line <- roc(as_tibble(mh_split$test)$vote96, fitted$decision.values)
plot(roc_line)

auc(roc_line)
## Area under the curve: 0.777

Polynomial kernel

mh_poly_tune <- tune(svm, vote96 ~ ., data = as_tibble(mh_split$train),
                    kernel = "polynomial",
                    range = list(cost = c(.001, .01, .1, 1, 5, 10, 100)))
summary(mh_poly_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost
##     1
## 
## - best performance: 0.284 
## 
## - Detailed performance results:
##    cost error dispersion
## 1 1e-03 0.315     0.0389
## 2 1e-02 0.315     0.0389
## 3 1e-01 0.304     0.0388
## 4 1e+00 0.284     0.0459
## 5 5e+00 0.300     0.0397
## 6 1e+01 0.301     0.0309
## 7 1e+02 0.311     0.0339
mh_poly <- mh_poly_tune$best.model
summary(mh_poly)
## 
## Call:
## best.tune(method = svm, train.x = vote96 ~ ., data = as_tibble(mh_split$train), 
##     ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), 
##     kernel = "polynomial")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  polynomial 
##        cost:  1 
##      degree:  3 
##       gamma:  0.125 
##      coef.0:  0 
## 
## Number of Support Vectors:  506
## 
##  ( 263 243 )
## 
## 
## Number of Classes:  2 
## 
## Levels: 
##  0 1
fitted <- predict(mh_poly, as_tibble(mh_split$test), decision.values = TRUE) %>%
  attributes

roc_poly <- roc(as_tibble(mh_split$test)$vote96, fitted$decision.values)
plot(roc_poly)

auc(roc_poly)
## Area under the curve: 0.73

Radial kernel

mh_rad_tune <- tune(svm, vote96 ~ ., data = as_tibble(mh_split$train),
                    kernel = "radial",
                    range = list(cost = c(.001, .01, .1, 1, 5, 10, 100)))
summary(mh_rad_tune)
## 
## Parameter tuning of 'svm':
## 
## - sampling method: 10-fold cross validation 
## 
## - best parameters:
##  cost
##     1
## 
## - best performance: 0.288 
## 
## - Detailed performance results:
##    cost error dispersion
## 1 1e-03 0.315     0.0535
## 2 1e-02 0.315     0.0535
## 3 1e-01 0.314     0.0509
## 4 1e+00 0.288     0.0524
## 5 5e+00 0.291     0.0561
## 6 1e+01 0.293     0.0568
## 7 1e+02 0.313     0.0537
mh_rad <- mh_rad_tune$best.model
summary(mh_rad)
## 
## Call:
## best.tune(method = svm, train.x = vote96 ~ ., data = as_tibble(mh_split$train), 
##     ranges = list(cost = c(0.001, 0.01, 0.1, 1, 5, 10, 100)), 
##     kernel = "radial")
## 
## 
## Parameters:
##    SVM-Type:  C-classification 
##  SVM-Kernel:  radial 
##        cost:  1 
##       gamma:  0.125 
## 
## Number of Support Vectors:  510
## 
##  ( 266 244 )
## 
## 
## Number of Classes:  2 
## 
## Levels: 
##  0 1
fitted <- predict(mh_rad, as_tibble(mh_split$test), decision.values = TRUE) %>%
  attributes

roc_rad <- roc(as_tibble(mh_split$test)$vote96, fitted$decision.values)
plot(roc_rad)

auc(roc_rad)
## Area under the curve: 0.749
plot(roc_line, print.auc = TRUE, col = "blue")
plot(roc_poly, print.auc = TRUE, col = "red", print.auc.y = .4, add = TRUE)
plot(roc_rad, print.auc = TRUE, col = "orange", print.auc.y = .3, add = TRUE)

SVM kernel CV training error rate
Linear 0.294
Polynomial 0.284
Radial 0.288

This time the SVM with the highest AUC is the linear model, followed by the radial and then the polynomial SVM. Interestingly, the linear SVM had the highest training error rate (cross-validated), followed by radial, and then polynomial with the lowest error rate. These are cross-validated measures, so it’s not as if they should be heavily biased. However they are all within 1 percentage point of each other, so the differences may not actually be that substantial. Further exploration could be warranted here.

We could tinker with the parameters for the polynomial and radial kernel SVMs, adjusting the number of degrees in the polynomial SVM and testing different constants \(\gamma\) for the radial SVM, again using 10-fold CV to select the optimal values. Instead though, let’s see how the SVM with the highest AUC (linear) stacks up with some of the other statistical learning methods we could apply.

Logistic regression

mh_logit <- glm(vote96 ~ ., data = as_tibble(mh_split$train), family = binomial)
summary(mh_logit)
## 
## Call:
## glm(formula = vote96 ~ ., family = binomial, data = as_tibble(mh_split$train))
## 
## Deviance Residuals: 
##    Min      1Q  Median      3Q     Max  
## -2.508  -1.049   0.534   0.855   1.948  
## 
## Coefficients:
##             Estimate Std. Error z value Pr(>|z|)    
## (Intercept) -4.00019    0.60162   -6.65  3.0e-11 ***
## mhealth_sum -0.08478    0.02795   -3.03   0.0024 ** 
## age          0.04332    0.00585    7.41  1.3e-13 ***
## educ         0.20305    0.03439    5.90  3.5e-09 ***
## black1       0.11542    0.23625    0.49   0.6252    
## female1      0.20224    0.16607    1.22   0.2233    
## married1     0.21052    0.18544    1.14   0.2563    
## inc10        0.06051    0.03143    1.93   0.0542 .  
## ---
## Signif. codes:  0 '***' 0.001 '**' 0.01 '*' 0.05 '.' 0.1 ' ' 1
## 
## (Dispersion parameter for binomial family taken to be 1)
## 
##     Null deviance: 1016.74  on 815  degrees of freedom
## Residual deviance:  876.12  on 808  degrees of freedom
## AIC: 892.1
## 
## Number of Fisher Scoring iterations: 4
fitted <- predict(mh_logit, as_tibble(mh_split$test), type = "response")
logit_err <- mean(as_tibble(mh_split$test)$vote96 != round(fitted))

roc_logit <- roc(as_tibble(mh_split$test)$vote96, fitted)
plot(roc_logit)

auc(roc_logit)
## Area under the curve: 0.778

The test error rate for the logistic regression model is 0.261.

Decision tree

mh_tree <- tree(vote96 ~ ., data = as_tibble(mh_split$train))
mh_tree
## node), split, n, deviance, yval, (yprob)
##       * denotes terminal node
## 
##  1) root 816 1000 1 ( 0 1 )  
##    2) age < 48.5 516  700 1 ( 0 1 )  
##      4) educ < 12.5 191  300 0 ( 1 0 )  
##        8) educ < 11.5 55   60 0 ( 1 0 ) *
##        9) educ > 11.5 136  200 1 ( 0 1 ) *
##      5) educ > 12.5 325  400 1 ( 0 1 )  
##       10) mhealth_sum < 4.5 259  300 1 ( 0 1 ) *
##       11) mhealth_sum > 4.5 66   90 0 ( 1 0 ) *
##    3) age > 48.5 300  300 1 ( 0 1 )  
##      6) educ < 12.5 153  200 1 ( 0 1 )  
##       12) inc10 < 1.08335 43   60 1 ( 0 1 ) *
##       13) inc10 > 1.08335 110  100 1 ( 0 1 ) *
##      7) educ > 12.5 147   60 1 ( 0 1 ) *
plot(mh_tree)
text(mh_tree, pretty = 0)

fitted <- predict(mh_tree, as_tibble(mh_split$test), type = "class")
tree_err <- mean(as_tibble(mh_split$test)$vote96 != fitted)

roc_tree <- roc(as.numeric(as_tibble(mh_split$test)$vote96), as.numeric(fitted))
plot(roc_tree)

auc(roc_tree)
## Area under the curve: 0.576

The test error rate for the decision tree model is 0.315.

Bagging

mh_bag <- randomForest(vote96 ~ ., data = as_tibble(mh_split$train),
                         mtry = 7)
mh_bag
## 
## Call:
##  randomForest(formula = vote96 ~ ., data = as_tibble(mh_split$train),      mtry = 7) 
##                Type of random forest: classification
##                      Number of trees: 500
## No. of variables tried at each split: 7
## 
##         OOB estimate of  error rate: 32.4%
## Confusion matrix:
##    0   1 class.error
## 0 89 168       0.654
## 1 96 463       0.172
varImpPlot(mh_bag)

fitted <- predict(mh_bag, as_tibble(mh_split$test), type = "prob")[,2]

roc_bag <- roc(as_tibble(mh_split$test)$vote96, fitted)
plot(roc_bag)

auc(roc_bag)
## Area under the curve: 0.714

Random forest

mh_rf <- randomForest(vote96 ~ ., data = as_tibble(mh_split$train))
mh_rf
## 
## Call:
##  randomForest(formula = vote96 ~ ., data = as_tibble(mh_split$train)) 
##                Type of random forest: classification
##                      Number of trees: 500
## No. of variables tried at each split: 2
## 
##         OOB estimate of  error rate: 30.4%
## Confusion matrix:
##    0   1 class.error
## 0 83 174       0.677
## 1 74 485       0.132
varImpPlot(mh_rf)

fitted <- predict(mh_rf, as_tibble(mh_split$test), type = "prob")[,2]

roc_rf <- roc(as_tibble(mh_split$test)$vote96, fitted)
plot(roc_rf)

auc(roc_rf)
## Area under the curve: 0.743

Compare the ROC curves

plot(roc_poly, print.auc = TRUE, col = "blue", print.auc.x = .2)
plot(roc_logit, print.auc = TRUE, col = "red", print.auc.x = .2, print.auc.y = .4, add = TRUE)
plot(roc_tree, print.auc = TRUE, col = "orange", print.auc.x = .2, print.auc.y = .3, add = TRUE)
plot(roc_bag, print.auc = TRUE, col = "green", print.auc.x = .2, print.auc.y = .2, add = TRUE)
plot(roc_rf, print.auc = TRUE, col = "purple", print.auc.x = .2, print.auc.y = .1, add = TRUE)

  • SVM (linear kernel)
  • Logistic regression
  • Decision tree
  • Bagging (\(n = 500\))
  • Random forest (\(n = 500, m = \sqrt{p}\))

Based solely on the test AUC, logistic regression and random forest provides the highest predictive accuracy, slightly better than the linear kernel SVM. Decision tree performs the worst, though admittedly AUC is biased against it since all decision trees produce are predictions, not probabilities, so the ROC “curve” is actually a point.

Session Info

devtools::session_info()
##  setting  value                       
##  version  R version 3.5.1 (2018-07-02)
##  system   x86_64, darwin15.6.0        
##  ui       X11                         
##  language (EN)                        
##  collate  en_US.UTF-8                 
##  tz       America/Chicago             
##  date     2019-01-02                  
## 
##  package      * version date       source        
##  assertthat     0.2.0   2017-04-11 CRAN (R 3.5.0)
##  backports      1.1.2   2017-12-13 CRAN (R 3.5.0)
##  base         * 3.5.1   2018-07-05 local         
##  base64enc      0.1-3   2015-07-28 CRAN (R 3.5.0)
##  bindr          0.1.1   2018-03-13 CRAN (R 3.5.0)
##  bindrcpp       0.2.2   2018-03-29 CRAN (R 3.5.0)
##  broom        * 0.5.0   2018-07-17 CRAN (R 3.5.0)
##  cellranger     1.1.0   2016-07-27 CRAN (R 3.5.0)
##  class          7.3-14  2015-08-30 CRAN (R 3.5.1)
##  cli            1.0.0   2017-11-05 CRAN (R 3.5.0)
##  colorspace     1.3-2   2016-12-14 CRAN (R 3.5.0)
##  compiler       3.5.1   2018-07-05 local         
##  crayon         1.3.4   2017-09-16 CRAN (R 3.5.0)
##  datasets     * 3.5.1   2018-07-05 local         
##  devtools       1.13.6  2018-06-27 CRAN (R 3.5.0)
##  digest         0.6.18  2018-10-10 cran (@0.6.18)
##  dplyr        * 0.7.8   2018-11-10 cran (@0.7.8) 
##  e1071        * 1.7-0   2018-07-28 CRAN (R 3.5.0)
##  evaluate       0.11    2018-07-17 CRAN (R 3.5.0)
##  forcats      * 0.3.0   2018-02-19 CRAN (R 3.5.0)
##  gbm          * 2.1.3   2017-03-21 CRAN (R 3.5.0)
##  ggplot2      * 3.1.0   2018-10-25 cran (@3.1.0) 
##  glue           1.3.0   2018-07-17 CRAN (R 3.5.0)
##  graphics     * 3.5.1   2018-07-05 local         
##  grDevices    * 3.5.1   2018-07-05 local         
##  grid         * 3.5.1   2018-07-05 local         
##  gridExtra    * 2.3     2017-09-09 CRAN (R 3.5.0)
##  gtable         0.2.0   2016-02-26 CRAN (R 3.5.0)
##  haven          1.1.2   2018-06-27 CRAN (R 3.5.0)
##  hms            0.4.2   2018-03-10 CRAN (R 3.5.0)
##  htmltools      0.3.6   2017-04-28 CRAN (R 3.5.0)
##  httr           1.3.1   2017-08-20 CRAN (R 3.5.0)
##  ISLR         * 1.2     2017-10-20 CRAN (R 3.5.0)
##  jsonlite       1.5     2017-06-01 CRAN (R 3.5.0)
##  knitr          1.20    2018-02-20 CRAN (R 3.5.0)
##  lattice      * 0.20-35 2017-03-25 CRAN (R 3.5.1)
##  lazyeval       0.2.1   2017-10-29 CRAN (R 3.5.0)
##  lubridate      1.7.4   2018-04-11 CRAN (R 3.5.0)
##  magrittr       1.5     2014-11-22 CRAN (R 3.5.0)
##  Matrix         1.2-14  2018-04-13 CRAN (R 3.5.1)
##  memoise        1.1.0   2017-04-21 CRAN (R 3.5.0)
##  methods      * 3.5.1   2018-07-05 local         
##  modelr       * 0.1.2   2018-05-11 CRAN (R 3.5.0)
##  munsell        0.5.0   2018-06-12 CRAN (R 3.5.0)
##  nlme           3.1-137 2018-04-07 CRAN (R 3.5.1)
##  parallel     * 3.5.1   2018-07-05 local         
##  pillar         1.3.0   2018-07-14 CRAN (R 3.5.0)
##  pkgconfig      2.0.2   2018-08-16 CRAN (R 3.5.1)
##  plyr           1.8.4   2016-06-08 CRAN (R 3.5.0)
##  pROC         * 1.12.1  2018-05-06 CRAN (R 3.5.0)
##  purrr        * 0.2.5   2018-05-29 CRAN (R 3.5.0)
##  R6             2.3.0   2018-10-04 cran (@2.3.0) 
##  randomForest * 4.6-14  2018-03-25 CRAN (R 3.5.0)
##  rcfss        * 0.1.5   2018-05-30 local         
##  Rcpp           1.0.0   2018-11-07 cran (@1.0.0) 
##  readr        * 1.1.1   2017-05-16 CRAN (R 3.5.0)
##  readxl         1.1.0   2018-04-20 CRAN (R 3.5.0)
##  rlang          0.3.0.1 2018-10-25 CRAN (R 3.5.0)
##  rmarkdown      1.10    2018-06-11 CRAN (R 3.5.0)
##  rprojroot      1.3-2   2018-01-03 CRAN (R 3.5.0)
##  rstudioapi     0.7     2017-09-07 CRAN (R 3.5.0)
##  rvest          0.3.2   2016-06-17 CRAN (R 3.5.0)
##  scales         1.0.0   2018-08-09 CRAN (R 3.5.0)
##  splines      * 3.5.1   2018-07-05 local         
##  stats        * 3.5.1   2018-07-05 local         
##  stringi        1.2.4   2018-07-20 CRAN (R 3.5.0)
##  stringr      * 1.3.1   2018-05-10 CRAN (R 3.5.0)
##  survival     * 2.42-6  2018-07-13 CRAN (R 3.5.0)
##  tibble       * 1.4.2   2018-01-22 CRAN (R 3.5.0)
##  tidyr        * 0.8.1   2018-05-18 CRAN (R 3.5.0)
##  tidyselect     0.2.5   2018-10-11 cran (@0.2.5) 
##  tidyverse    * 1.2.1   2017-11-14 CRAN (R 3.5.0)
##  titanic      * 0.1.0   2015-08-31 CRAN (R 3.5.0)
##  tools          3.5.1   2018-07-05 local         
##  tree         * 1.0-39  2018-03-17 CRAN (R 3.5.0)
##  utils        * 3.5.1   2018-07-05 local         
##  withr          2.1.2   2018-03-15 CRAN (R 3.5.0)
##  xml2           1.2.0   2018-01-24 CRAN (R 3.5.0)
##  yaml           2.2.0   2018-07-25 CRAN (R 3.5.0)

  1. Though they can also be applied to regression on continuous response variables.

  2. Remember that we can use the perpendicular distance from the hyperplane as a measure of confidence in our predictions, so the new training observation diminishes our confidence for quite a few of the red training observations.

  3. Like how boosting uses the residuals of the response variable \(Y\), rather than \(Y\) itself.

  4. Why use the validation set approach? We’ve discussed the inadequacies of it before. We could use \(k\)-fold cross validation instead, however setting this up with the proper code would be much more complicated. When conducting exploratory analysis, you don’t necessarily need to do this on your first pass through the data. Certainly I recommend using CV to validate your models and compare them before publishing anything, but for this application I think the validation set approach works fine.

LS0tCnRpdGxlOiAiU3RhdGlzdGljYWwgbGVhcm5pbmc6IHN1cHBvcnQgdmVjdG9yIG1hY2hpbmVzIgphdXRob3I6ICJNQUNTIDMwMTAwIC0gUGVyc3BlY3RpdmVzIG9uIENvbXB1dGF0aW9uYWwgTW9kZWxpbmciCm91dHB1dDoKICBodG1sX2RvY3VtZW50OgogICAgdG9jOiB0cnVlCiAgICB0b2NfZmxvYXQ6IHRydWUKICAgIGNvZGVfZm9sZGluZzogaGlkZQotLS0KCmBgYHtyIHNldHVwLCBpbmNsdWRlID0gRkFMU0V9CmtuaXRyOjpvcHRzX2NodW5rJHNldChjYWNoZSA9IFRSVUUsCiAgICAgICAgICAgICAgICAgICAgICBtZXNzYWdlID0gRkFMU0UsCiAgICAgICAgICAgICAgICAgICAgICB3YXJuaW5nID0gRkFMU0UpCmBgYAoKIyBPYmplY3RpdmVzCgoqIERlZmluZSB0aGUgbWF4aW1hbCBtYXJnaW4gY2xhc3NpZmllcgoqIERlZmluZSB0aGUgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciBhbmQgZGlzY3VzcyB0aGUgbG9naWMgb2YgdGhpcyBhcHByb2FjaAoqIERlZmluZSBzdXBwb3J0IHZlY3RvciBtYWNoaW5lcyAoU1ZNKSBhbmQgbm9uLWxpbmVhciBkZWNpc2lvbiBib3VuZGFyaWVzCiogQXBwbHkgU1ZNIGNsYXNzaWZpY2F0aW9uIHRvIGV4YW1wbGUgZGF0YSBzZXRzIGFuZCBjb21wYXJlIHdpdGggYWx0ZXJuYXRpdmUgc3RhdGlzdGljYWwgbGVhcm5pbmcgbW9kZWxzCgpgYGB7ciBwYWNrYWdlcywgY2FjaGUgPSBGQUxTRSwgbWVzc2FnZSA9IEZBTFNFLCB3YXJuaW5nID0gRkFMU0V9CmxpYnJhcnkodGlkeXZlcnNlKQpsaWJyYXJ5KGZvcmNhdHMpCmxpYnJhcnkoYnJvb20pCmxpYnJhcnkobW9kZWxyKQpsaWJyYXJ5KHRyZWUpCmxpYnJhcnkocmFuZG9tRm9yZXN0KQpsaWJyYXJ5KHN0cmluZ3IpCmxpYnJhcnkoSVNMUikKbGlicmFyeSh0aXRhbmljKQpsaWJyYXJ5KHJjZnNzKQpsaWJyYXJ5KHBST0MpCmxpYnJhcnkoZ2JtKQpsaWJyYXJ5KGUxMDcxKQpsaWJyYXJ5KGdyaWQpCmxpYnJhcnkoZ3JpZEV4dHJhKQoKb3B0aW9ucyhkaWdpdHMgPSAzKQpzZXQuc2VlZCgxMjM0KQp0aGVtZV9zZXQodGhlbWVfbWluaW1hbCgpKQpgYGAKCioqU3VwcG9ydCB2ZWN0b3IgbWFjaGluZXMqKiAoU1ZNcykgYXJlIGEgcG9wdWxhciBzdGF0aXN0aWNhbCBsZWFybmluZyBtZXRob2QgZm9yIGNsYXNzaWZpY2F0aW9uIHRhc2tzLl5bVGhvdWdoIHRoZXkgY2FuIGFsc28gYmUgYXBwbGllZCB0byByZWdyZXNzaW9uIG9uIGNvbnRpbnVvdXMgcmVzcG9uc2UgdmFyaWFibGVzLl0gU1ZNcyBidWlsZCBvbiBzZXZlcmFsIGltcG9ydGFudCBjb25jZXB0cywgdGhhdCB3aGlsZSByZWxhdGVkIGFyZSBkaXN0aW5jdCBmcm9tIG9uZSBhbm90aGVyLiBXZSB3aWxsIGZpcnN0IGRpc2N1c3MgdGhlIGxvZ2ljIG9mIHRoZXNlIGluZGl2aWR1YWwgY29tcG9uZW50cywgdGhlbiBkZW1vbnN0cmF0ZSBob3cgdG8gZXN0aW1hdGUgYW5kIGludGVycHJldCBTVk1zLCBhbmQgY29tcGFyZSBtb2RlbCByZXN1bHRzIHVzaW5nIHRoaXMgbWV0aG9kIHRvIG90aGVyIHN0YXRpc3RpY2FsIGxlYXJuaW5nIHByb2NlZHVyZXMgd2UgaGF2ZSBkaXNjdXNzZWQgc28gZmFyLgoKIyBNYXhpbWFsIG1hcmdpbiBjbGFzc2lmaWVyCgojIyBIeXBlcnBsYW5lcwoKSW4gJHAkLWRpbWVuc2lvbmFsIHNwYWNlLCBhICoqaHlwZXJwbGFuZSoqIGlzIGEgZmxhdCBzdWJzcGFjZSBvZiAkcCAtIDEkIGRpbWVuc2lvbnMgdGhhdCBpcyAqYWZmaW5lKiAoZG9lcyBub3QgbmVlZCB0byBwYXNzIHRocm91Z2ggdGhlIG9yaWdpbikuIEluIHR3byBkaW1lbnNpb25zLCBhIGh5cGVycGxhbmUgaXMgYSBmbGF0IG9uZS1kaW1lbnNpb25hbCBzdWJzcGFjZSAoYWxzbyBrbm93biBhcyBhICoqbGluZSoqKS4gSW4gdGhyZWUgZGltZW5zaW9ucywgYSBoeXBlciBwbGFuZSBpcyBhIGZsYXQgdHdvLWRpbWVuc2lvbmFsIHN1YnNwYWNlIChhbHNvIGtub3duIGFzIGEgKipwbGFuZSoqKS4gSW4gaGlnaGVyIGRpbWVuc2lvbnMgaXQgZ2V0cyBoYXJkZXIgdG8gdmlzdWFsaXplIHRoaXMgY29uY2VwdCwgYnV0IHRoZSBkZWZpbml0aW9uIHN0aWxsIGhvbGRzIHRydWUuCgpJbiB0d28gZGltZW5zaW9ucywgdGhlIG1hdGhlbWF0aWNhbCBlcXVhdGlvbiBmb3IgYSBoeXBlcnBsYW5lIGlzOgoKJCRcYmV0YV8wICsgXGJldGFfMSBYXzEgKyBcYmV0YV8yIFhfMiA9IDAkJAoKQW55ICRYID0gKFhfMSwgWF8yKV5UJCBmb3Igd2hpY2ggdGhpcyBlcXVhdGlvbiBob2xkcyBpcyBhIHBvaW50IG9uIHRoZSBoeXBlcnBsYW5lIChsaW5lKS4gVGhpcyBmdW5jdGlvbmFsIGZvcm0gZ2VuZXJhbGl6ZXMgdG8gJHAkIGRpbWVuc2lvbnMgcXVpdGUgZWFzaWx5OgoKJCRcYmV0YV8wICsgXGJldGFfMSBYXzEgKyBcYmV0YV8yIFhfMiArIFxkb3RzICsgXGJldGFfcCBYX3AgPSAwJCQKCkFnYWluLCBmb3IgYW55IHBvaW50ICRYID0gKFhfMSwgWF8yLCBcZG90cywgWF9wKV5UJCBpbiAkcCQtZGltZW5zaW9uYWwgc3BhY2UgKGkuZS4gYSB2ZWN0b3Igb2YgbGVuZ3RoICRwJCkgdGhhdCBlcXVhbHMgMCwgdGhlbiAkWCQgbGllcyBvbiB0aGUgaHlwZXJwbGFuZS4KCkZvciAkWCQgdGhhdCBkb2VzIG5vdCBtZWV0IHRoaXMgY29uZGl0aW9uLCB0aGVuIHRoZSBkYXRhIHBvaW50IGxpZXMgb24gZWl0aGVyIHNpZGUgb2YgdGhlIGh5cGVycGxhbmU6CgokJFxiZXRhXzAgKyBcYmV0YV8xIFhfMSArIFxiZXRhXzIgWF8yICsgXGRvdHMgKyBcYmV0YV9wIFhfcCA+IDAkJAoKJCRcYmV0YV8wICsgXGJldGFfMSBYXzEgKyBcYmV0YV8yIFhfMiArIFxkb3RzICsgXGJldGFfcCBYX3AgPCAwJCQKClRoZSBoeXBlcnBsYW5lIHRoZXJlZm9yZSBkaXZpZGVzIHRoZSAkcCQtZGltZW5zaW9uYWwgc3BhY2UgaW50byB0d28gaGFsdmVzLiBUbyBkZXRlcm1pbmUgb24gd2hpY2ggc2lkZSBvZiB0aGUgaHlwZXJwbGFuZSBhbiBvYnNlcnZhdGlvbiBsaWVzLCB3ZSBzaW1wbHkgY2FsY3VsYXRlIHRoZSBzaWduIG9mIHRoZSBjb3JyZXNwb25kaW5nIGh5cGVycGxhbmUgZXF1YXRpb24uCgpgYGB7ciBoeXBlcnBsYW5lfQpzaW1faHlwZXIgPC0gZGF0YV9mcmFtZSh4MSA9IHNlcSgtMS41LCAxLjUsIGxlbmd0aC5vdXQgPSAyMCksCiAgICAgICAgICAgICAgICAgICAgICAgIHgyID0gc2VxKC0xLjUsIDEuNSwgbGVuZ3RoLm91dCA9IDIwKSkgJT4lCiAgZXhwYW5kKHgxLCB4MikgJT4lCiAgbXV0YXRlKHkgPSAxICsgMiAqIHgxICsgMyAqIHgyLAogICAgICAgICBncm91cCA9IGlmZWxzZSh5IDwgMCwgLTEsCiAgICAgICAgICAgICAgICAgICAgICAgIGlmZWxzZSh5ID4gMCwgMSwgMCkpLAogICAgICAgICBncm91cCA9IGZhY3Rvcihncm91cCkpCgpzaW1faHlwZXJfbGluZSA8LSBkYXRhX2ZyYW1lKHgxID0gc2VxKC0xLjUsIDEuNSwgbGVuZ3RoLm91dCA9IDIwKSwKICAgICAgICAgICAgICAgICAgICAgICAgICAgICB4MiA9ICgtMSAtIDIgKiB4MSkgLyAzKQoKZ2dwbG90KHNpbV9oeXBlciwgYWVzKHgxLCB4MiwgY29sb3IgPSBncm91cCkpICsKICBnZW9tX3BvaW50KCkgKwogIGdlb21fbGluZShkYXRhID0gc2ltX2h5cGVyX2xpbmUsIGFlcyhjb2xvciA9IE5VTEwpKSArCiAgbGFicyh0aXRsZSA9ICJIeXBlcnBsYW5lIGluIHR3byBkaW1lbnNpb25zIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKYGBgCgojIyBDbGFzc2lmaWNhdGlvbiB1c2luZyBhIHNlcGFyYXRpbmcgaHlwZXJwbGFuZQoKTGV0J3MgcmVwcmVzZW50IGEgaHlwb3RoZXRpY2FsIGNsYXNzaWZpY2F0aW9uIHByb2JsZW0gYXMgdGhlIGZvbGxvd2luZzogc3VwcG9zZSB3ZSBoYXZlIGFuICRuIFx0aW1lcyBwJCBkYXRhIG1hdHJpeCAkXG1hdGhiZntYfSQgdGhhdCBjb25zaXN0cyBvZiAkbiQgdHJhaW5pbmcgb2JzZXJ2YXRpb25zIHdpdGggJHAkIHByZWRpY3RvcnMgaW4gJHAkLWRpbWVuc2lvbmFsIHNwYWNlOgoKJCR4XzEgPSBcYmVnaW57cG1hdHJpeH0KICB4X3sxMX0gXFwKICBcdmRvdHMgXFwKICB4X3sxcH0KIFxlbmR7cG1hdHJpeH0sCiBcZG90cywgeF9uID0gXGJlZ2lue3BtYXRyaXh9CiAgeF97bjF9IFxcCiAgXHZkb3RzIFxcCiAgeF97bnB9CiBcZW5ke3BtYXRyaXh9JCQKClRoZXNlIG9ic2VydmF0aW9ucyBmYWxsIGludG8gb25lIG9mIHR3byBjbGFzc2VzICR5XzEsIFxkb3RzLCB5X24gXGluIFx7LTEsIDEgXH0kIHdoZXJlICQtMSQgYW5kICQxJCByZXByZXNlbnQgdHdvIHNlcGFyYXRlIGNsYXNzZXMgb3IgY2F0ZWdvcmllcy4gV2UgYWxzbyBoYXZlIGEgdGVzdCBvYnNlcnZhdGlvbiAkeF4qJCB3aGljaCBpcyBhICRwJC12ZWN0b3Igb2Ygb2JzZXJ2ZWQgcHJlZGljdG9ycyAkeF4qID0gKHhfMV4qLCBcZG90cywgeF9wXiopJC4gV2Ugd2FudCB0byBkZXZlbG9wIGEgbW9kZWwgdGhhdCBjbGFzc2lmaWVzIHRoZSB0ZXN0IG9ic2VydmF0aW9uIGNvcnJlY3RseSBnaXZlbiBvdXIga25vd2xlZGdlIG9mIHRoZSB0cmFpbmluZyBvYnNlcnZhdGlvbnMuIFByZXZpb3VzbHkgd2UgaGF2ZSB1c2VkIG1ldGhvZHMgc3VjaCBhcyBsb2dpc3RpYyByZWdyZXNzaW9uICh3aGVyZSB0aGUgcmVzcG9uc2UgdmFyaWFibGUgaXMgY29kZWQgJFx7MCwgMSBcfSQpIGFuZCBkZWNpc2lvbiB0cmVlcyB0byBwZXJmb3JtIHRoaXMgdGFzay4gTm93IHdlIHdhbnQgdG8gdXNlIGEgaHlwZXJwbGFuZSB0byAqKnNlcGFyYXRlKiogdGhlIHRyYWluaW5nIG9ic2VydmF0aW9ucyBpbnRvIHRoZSB0d28gcG9zc2libGUgY2xhc3Nlcy4KCkEgKipzZXBhcmF0aW5nIGh5cGVycGxhbmUqKiBwZXJmZWN0bHkgc2VwYXJhdGVzIHRyYWluaW5nIG9ic2VydmF0aW9ucyBpbnRvIHRoZWlyIGNsYXNzIGxhYmVscy4gT2JzZXJ2YXRpb25zIGluIHRoZSBibHVlIGNsYXNzIGFyZSBjb2RlZCBhcyAkeV9pID0gMSQgdGhvc2UgZnJvbSB0aGUgcmVkIGNsYXNzIGFzICR5X2kgPSAtMSQuIFNvIGEgc2VwYXJhdGluZyBoeXBlcnBsYW5lIHRha2VzIG9uIHRoZSBwcm9wZXJ0aWVzOgoKJCRcYmV0YV8wICsgXGJldGFfMSB4X3tpMX0gKyBcZG90cyArIFxiZXRhX3AgeF97aXB9ID4gMCwgXHRleHR7aWYgfSB5X2kgPSAxJCQKJCRcYmV0YV8wICsgXGJldGFfMSB4X3tpMX0gKyBcZG90cyArIFxiZXRhX3AgeF97aXB9IDwgMCwgXHRleHR7aWYgfSB5X2kgPSAtMSQkCgpgYGB7ciBzaW19CnNpbSA8LSBkYXRhX2ZyYW1lKHgxID0gcnVuaWYoMjAsIC0yLCAyKSwKICAgICAgICAgICAgICAgICAgeDIgPSBydW5pZigyMCwgLTIsIDIpLAogICAgICAgICAgICAgICAgICB5ID0gaWZlbHNlKDEgKyAyICogeDEgKyAzICogeDIgPCAwLCAtMSwgMSkpICU+JQogIG11dGF0ZV9lYWNoKGZ1bnMoaWZlbHNlKHkgPT0gMSwgLiArIDEuNSwgLikpLCB4MikgJT4lCiAgbXV0YXRlKHkgPSBmYWN0b3IoeSwgbGV2ZWxzID0gYygtMSwgMSkpKSAlPiUKICBtdXRhdGUobGluZTEgPSAoLTEgLSAyICogeDEpIC8gMywKICAgICAgICAgbGluZTIgPSAuNSArICgtMSAtIDEuNSAqIHgxKSAvIDMsCiAgICAgICAgIGxpbmUzID0gLjI1IC0gLjA1ICogeDEpCgpnZ3Bsb3Qoc2ltLCBhZXMoeDEpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHgyLCBjb2xvciA9IHkpKSArCiAgZ2VvbV9saW5lKGFlcyh5ID0gbGluZTEsIGNvbG9yID0gTlVMTCkpICsKICBnZW9tX2xpbmUoYWVzKHkgPSBsaW5lMiwgY29sb3IgPSBOVUxMKSkgKwogIGdlb21fbGluZShhZXMoeSA9IGxpbmUzLCBjb2xvciA9IE5VTEwpKSArCiAgbGFicyh0aXRsZSA9ICJFeGFtcGxlcyBvZiBzZXBhcmF0aW5nIGh5cGVycGxhbmVzIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKYGBgCgpJZiBhIHNlcGFyYXRpbmcgaHlwZXJwbGFuZSBleGlzdHMsIHRoZW4gd2UgY2FuIGNsYXNzaWZ5IHRlc3Qgb2JzZXJ2YXRpb25zIGJhc2VkIG9uIHRoZWlyIGxvY2F0aW9uIHJlbGF0aXZlIHRvIHRoZSBoeXBlcnBsYW5lOgoKYGBge3Igc2ltLWRlY2lzaW9ufQpzaW1fbW9kIDwtIHN2bSh5IH4geDEgKyB4MiwgZGF0YSA9IHNpbSwga2VybmVsID0gImxpbmVhciIsIGNvc3QgPSAxZTA1LAogICAgICAgICAgICAgICBzY2FsZSA9IEZBTFNFKQpzaW1fY29lZiA8LSBjKHNpbV9tb2QkcmhvLCB0KHNpbV9tb2QkY29lZnMpICUqJSBzaW1fbW9kJFNWKQoKc2ltX2dyaWQgPC0gZGF0YV9mcmFtZSh4MSA9IHNlcSgtMiwgMiwgbGVuZ3RoLm91dCA9IDEwMCksCiAgICAgICAgICAgICAgICAgIHgyID0gc2VxKC0yLCAzLjUsIGxlbmd0aC5vdXQgPSAxMDApKSAlPiUKICBleHBhbmQoeDEsIHgyKSAlPiUKICBtdXRhdGUoeSA9IGlmZWxzZSgtc2ltX2NvZWZbWzFdXSArIHNpbV9jb2VmW1syXV0gKiB4MSArIHNpbV9jb2VmW1szXV0gKiB4MiA+IDAsIC0xLCAxKSwKICAgICAgICAgeSA9IGZhY3Rvcih5LCBsZXZlbHMgPSBjKC0xLCAxKSkpCgpzaW1fcGxhbmUgPC0gZGF0YV9mcmFtZSh4MSA9IHNlcSgtMiwgMiwgbGVuZ3RoLm91dCA9IDEwMCksCiAgICAgICAgICAgICAgICAgICAgICAgIHgyID0gKHNpbV9jb2VmW1sxXV0gLSBzaW1fY29lZltbMl1dICogeDEpIC8gc2ltX2NvZWZbWzNdXSkKCmdncGxvdChzaW0sIGFlcyh4MSkpICsKICBnZW9tX3BvaW50KGRhdGEgPSBzaW1fZ3JpZCwgYWVzKHgxLCB4MiwgY29sb3IgPSB5KSwgYWxwaGEgPSAuMjUsIHNpemUgPSAuMjUpICsKICBnZW9tX3BvaW50KGFlcyh5ID0geDIsIGNvbG9yID0geSkpICsKICBnZW9tX2xpbmUoZGF0YSA9IHNpbV9wbGFuZSwgYWVzKHgxLCB4MikpICsKICBsYWJzKHRpdGxlID0gIk1heGltYWwgbWFyZ2luIGNsYXNzaWZpY2F0aW9uIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKYGBgCgpDbGFzc2lmaWNhdGlvbnMgYXJlIGJhc2VkIG9mZiB0aGUgc2lnbiBvZiAkZih4XiopID0gXGJldGFfMCArIFxiZXRhXzEgeF8xXiogKyBcZG90cyArIFxiZXRhX3AgeF9wXiokLiBJZiAkZih4XiopJCBpcyBwb3NpdGl2ZSwgdGhlbiB3ZSBwcmVkaWN0IHRoZSB0ZXN0IG9ic2VydmF0aW9uIGlzICQxJC4gSWYgJGYoeF4qKSQgaXMgbmVnYXRpdmUsIHRoZW4gd2UgcHJlZGljdCB0aGUgdGVzdCBvYnNlcnZhdGlvbiBpcyAkLTEkLiBXZSBjYW4gYWxzbyBjb25zaWRlciB0aGUgKiptYWduaXR1ZGUqKiBvZiAkZih4XiopJDogdGhlIGZhcnRoZXIgdGhlIG1hZ25pdHVkZSBpcyBhd2F5IGZyb20gemVybywgdGhlbiB0aGUgZmFydGhlciB0aGUgdGVzdCBvYnNlcnZhdGlvbiBmYWxscyBmcm9tIHRoZSBoeXBlcnBsYW5lLiBXZSBjYW4gYmUgbW9yZSBjb25maWRlbnQgb2Ygb3VyIHByZWRpY3Rpb25zIGZvciBvYnNlcnZhdGlvbnMgZmFyIGZyb20gdGhlIGh5cGVycGxhbmUsIGFuZCBsZXNzIHNvIGZvciBvYnNlcnZhdGlvbnMgbmVhciB0aGUgaHlwZXJwbGFuZSAoaS5lLiAkZih4XiopJCBjbG9zZSB0byB6ZXJvKS4gVGhlIGNsYXNzaWZpZXIgcmVzdWx0aW5nIGZyb20gdGhlIHNlcGFyYXRpbmcgaHlwZXJwbGFuZSAkZih4XiopID0gXGJldGFfMCArIFxiZXRhXzEgeF8xXiogKyBcZG90cyArIFxiZXRhX3AgeF9wXiokIGlzIGEgKipsaW5lYXIgZGVjaXNpb24gYm91bmRhcnkqKiBiZWNhdXNlIHRoZSBmdW5jdGlvbiBpdHNlbGYgaXMgYSBsaW5lYXIgZm9ybS4KCiMjIE1heGltYWwgbWFyZ2luIGNsYXNzaWZpZXIKCkFzIHdlIHNhdyBwcmV2aW91c2x5LCBpZiB0aGUgZGF0YSBjYW4gYmUgcGVyZmVjdGx5IHNlcGFyYXRlZCBieSBhIGh5cGVycGxhbmUgaXQgaXMgbGlrZWx5IHRydWUgdGhhdCB0aGVyZSBhcmUgKiptdWx0aXBsZSBwb3RlbnRpYWwgc2VwYXJhdGluZyBoeXBlcnBsYW5lcyoqLiBXZSBuZWVkIGEgbWV0aG9kIGZvciBpZGVudGlmeWluZyB0aGUgKm9wdGltYWwqIHNlcGFyYXRpbmcgaHlwZXJwbGFuZS4gVGhpcyBpcyBrbm93biBhcyB0aGUgKiptYXhpbWFsIG1hcmdpbiBoeXBlcnBsYW5lKiosIHdoaWNoIGlzIHRoZSBzZXBhcmF0aW5nIGh5cGVycGxhbmUgdGhhdCBpcyBmYXJ0aGVzdCBmcm9tIHRoZSB0cmFpbmluZyBvYnNlcnZhdGlvbnMuIFRoZSAqKm1hcmdpbioqIGlzIHRoZSBzbWFsbGVzdCBwb3NzaWJsZSAocGVycGVuZGljdWxhcikgZGlzdGFuY2UgYmV0d2VlbiBhIHRyYWluaW5nIG9ic2VydmF0aW9uIGFuZCB0aGUgc2VwYXJhdGluZyBoeXBlcnBsYW5lLiBUaGlzIGRpc3RhbmNlIGlzIHNpbXBseSAkXGhhdHtmfSh4X2kpJC4gVGhlIG1heGltYWwgbWFyZ2luIGh5cGVycGxhbmUgZGVmaW5lcyB0aGUgaHlwZXJwbGFuZSB0aGF0IG1pbmltaXplcyB0aGUgbWFyZ2luYWwgZGlzdGFuY2UgYWNyb3NzIGFsbCB0cmFpbmluZyBvYnNlcnZhdGlvbnMsIGFuZCBjYW4gYmUgdXNlZCB0byBjbGFzc2lmeSB0aGUgdGVzdCBvYnNlcnZhdGlvbiAkeF4qJCBiYXNlZCBvbiB3aGljaCBzaWRlIG9mIHRoZSBoeXBlcnBsYW5lIGl0IGxpZXMuIFRoaXMgaXMga25vd24gYXMgdGhlICoqbWF4aW1hbCBtYXJnaW4gY2xhc3NpZmllcioqLiBUaGUgZXhwZWN0YXRpb24gaXMgdGhhdCBhIGNsYXNzaWZpZXIgd2l0aCBhIGxhcmdlIG1hcmdpbiBmb3IgdGhlIHRyYWluaW5nIG9ic2VydmF0aW9ucyB3aWxsIGFsc28gaGF2ZSBhIGxhcmdlIG1hcmdpbiBmb3IgdGhlIHRlc3Qgb2JzZXJ2YXRpb25zLCBsZWFkaW5nIHRvIGFjY3VyYXRlIGNsYXNzaWZpY2F0aW9ucy4gQXMgd2l0aCB0aGUgb3RoZXIgbWV0aG9kcyB3ZSBoYXZlIGRpc2N1c3NlZCBzbyBmYXIsIHRoaXMgaXMgYW4gYXNzdW1wdGlvbiBhbmQgaXQgaXMgc3RpbGwgcG9zc2libGUgdG8gb3ZlcmZpdCB0aGUgdHJhaW5pbmcgZGF0YSB1c2luZyB0aGUgbWF4aW1hbCBtYXJnaW4gY2xhc3NpZmllci4KCmBgYHtyIHNpbS1tYXJnaW59CnNpbV9wcmVkIDwtIHByZWRpY3Qoc2ltX21vZCwgc2ltLCBkZWNpc2lvbi52YWx1ZXMgPSBUUlVFKQpzaW1fZGlzdCA8LSBhdHRyKHNpbV9wcmVkLCAiZGVjaXNpb24udmFsdWVzIikKCmdncGxvdChzaW0sIGFlcyh4MSkpICsKICBnZW9tX3BvaW50KGFlcyh5ID0geDIsIGNvbG9yID0geSkpICsKICBnZW9tX3BvaW50KGRhdGEgPSBzaW1fZ3JpZCwgYWVzKHgxLCB4MiwgY29sb3IgPSB5KSwgYWxwaGEgPSAuMSwgc2l6ZSA9IC4yNSkgKwogIGdlb21fbGluZShkYXRhID0gc2ltX3BsYW5lLCBhZXMoeDEsIHgyKSkgKwogICAgZ2VvbV9saW5lKGRhdGEgPSBtdXRhdGUoc2ltX3BsYW5lLCB4MiA9IHgyIC0gbWluKGFicyhzaW1fZGlzdCkpKSwKICAgICAgICAgICAgICBhZXMoeDEsIHgyKSwgbGluZXR5cGUgPSAyKSArCiAgICBnZW9tX2xpbmUoZGF0YSA9IG11dGF0ZShzaW1fcGxhbmUsIHgyID0geDIgKyBtaW4oYWJzKHNpbV9kaXN0KSkpLAogICAgICAgICAgICAgIGFlcyh4MSwgeDIpLCBsaW5ldHlwZSA9IDIpICsKICBsYWJzKHRpdGxlID0gIk1heGltYWwgbWFyZ2luIGNsYXNzaWZpY2F0aW9uIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKYGBgCgpUd28gb2JzZXJ2YXRpb25zIGFyZSBlcXVpZGlzdGFudCBmcm9tIHRoZSBtYXhpbWFsIG1hcmdpbiBoeXBlcnBsYW5lIGFuZCBsaWUgYWxvbmcgdGhlIGRhc2hlZCBsaW5lcyBpbmRpY2F0aW5nIHRoZSB3aWR0aCBvZiB0aGUgbWFyZ2luLiBUaGVzZSBvYnNlcnZhdGlvbnMgYXJlIGNhbGxlZCB0aGUgKipzdXBwb3J0IHZlY3RvcnMqKi4gVGhleSBhcmUgdmVjdG9ycyBpbiAkcCQtZGltZW5zaW9uYWwgc3BhY2UgYW5kICJzdXBwb3J0IiB0aGUgbWF4aW1hbCBtYXJnaW4gaHlwZXJwbGFuZSBiZWNhdXNlIGlmIHRoZSBvYnNlcnZhdGlvbnMgc2hpZnRlZCBhdCBhbGwgaW4gdGhlaXIgcHJlZGljdG9yIHZhbHVlcyAkWCQsIHRoZW4gdGhlIG1heGltYWwgbWFyZ2luIGh5cGVycGxhbmUgd291bGQgc2hpZnQgYXMgd2VsbC4gSW4gZmFjdCwgdGhlIG1heGltYWwgbWFyZ2luIGh5cGVycGxhbmUgaXMgZGVmaW5lZCBlbnRpcmVseSBieSB0aGUgc3VwcG9ydCB2ZWN0b3JzOyBjaGFuZ2VzIHRvIHRoZSBvdGhlciBvYnNlcnZhdGlvbnMgd291bGQgbm90IGVmZmVjdCB0aGUgc2VwYXJhdGluZyBoeXBlcnBsYW5lIGFzIGxvbmcgYXMgdGhlIGNoYW5nZWQgb2JzZXJ2YXRpb25zIGRvIG5vdCBjcm9zcyB0aGUgYm91bmRhcnkgc2V0IGJ5IHRoZSBtYXJnaW4uCgojIyMgQ29uc3RydWN0aW5nIHRoZSBtYXhpbWFsIG1hcmdpbiBoeXBlcnBsYW5lCgpDb25zdHJ1Y3RpbmcgdGhlIG1heGltYWwgbWFyZ2luIGh5cGVycGxhbmUgaXMgYSAocmVsYXRpdmVseSkgc3RyYWlnaHQgZm9yd2FyZCBhZmZhaXIuIENvbnNpZGVyIGEgc2V0IG9mICRuJCB0cmFpbmluZyBvYnNlcnZhdGlvbnMgd2l0aCBzb21lIG51bWJlciBvZiByZWFsIG51bWJlciBwcmVkaWN0b3JzICR4XzEsIFxkb3RzLCB4X24gXGluIFxtYXRoYmJ7Un1ecCQgYW5kIGFzc29jaWF0ZWQgY2xhc3MgbGFiZWxzICR5XzEsIFxkb3RzLCB5X24gXGluIFx7LTEsIDFcfSQuIFdlIHdhbnQgdG8gc29sdmUgdGhlIG9wdGltaXphdGlvbiBwcm9ibGVtOgoKJCRcYmVnaW57YWxpZ25lZH0KJiBcdW5kZXJzZXR7XGJldGFfMCwgXGJldGFfMSwgXGRvdHMsIFxiZXRhX3B9e1x0ZXh0e21heGltaXplfX0gJiAmIE0gXFwKJiBcdGV4dHtzLnQufSAmICYgIFxzdW1fe2o9MX1ecCBcYmV0YV9qXjIgPSAxLCBcXAomICYgJiB5X2koXGJldGFfMCArIFxiZXRhXzEgeF97aTF9ICsgXGJldGFfMiB4X3tpMn0gKyBcZG90cyArIFxiZXRhX3AgeF97aXB9KSBcZ2VxIE0gXDsgXGZvcmFsbCBcOyBpID0gMSwgXGRvdHMsIG4gXFwKXGVuZHthbGlnbmVkfSQkCgpUaGlzIGlzIHNpbXBsZXIgdGhhbiBpdCBsb29rcy4gJHlfaShcYmV0YV8wICsgXGJldGFfMSB4X3tpMX0gKyBcYmV0YV8yIHhfe2kyfSArIFxkb3RzICsgXGJldGFfcCB4X3tpcH0pIFxnZXEgTSBcOyBcZm9yYWxsIFw7IGkgPSAxLCBcZG90cywgbiQgcmVxdWlyZXMgdGhlIG1heGltYWwgbWFyZ2luIGh5cGVycGxhbmUgdG8gc29ydCBvYnNlcnZhdGlvbnMgb24gdGhlIGNvcnJlY3Qgc2lkZSBvZiB0aGUgaHlwZXJwbGFuZSB3aXRoIHNvbWUgYW1vdW50IG9mIGN1c2hpb24sIHByb3ZpZGVkICRNJCBpcyBwb3NpdGl2ZS4gVGhlIHJlcXVpcmVtZW50ICRcc3VtX3tqPTF9XnAgXGJldGFfal4yID0gMSQgbWVhbnMgdGhhdCBub3Qgb25seSBhcmUgdGhlIG9ic2VydmF0aW9ucyBzb3J0ZWQgb250byB0aGUgY29ycmVjdCBzaWRlcyBvZiB0aGUgaHlwZXJwbGFuZSwgYnV0IHRoYXQgdGhlIGZ1bmN0aW9uICR5X2koXGJldGFfMCArIFxiZXRhXzEgeF97aTF9ICsgXGJldGFfMiB4X3tpMn0gKyBcZG90cyArIFxiZXRhX3AgeF97aXB9KSQgZGVmaW5lcyB0aGUgKipwZXJwZW5kaWN1bGFyIGRpc3RhbmNlKiogYmV0d2VlbiB0aGUgb2JzZXJ2YXRpb24gJHlfaSQgYW5kIHRoZSBoeXBlcnBsYW5lLiBUaGVyZWZvcmUgJE0kIGRlZmluZXMgdGhlIG1hcmdpbiBvZiB0aGUgaHlwZXJwbGFuZSAoaS5lLiB0aGUgYW1vdW50IG9mIGN1c2hpb24gYmV0d2VlbiB0aGUgaHlwZXJwbGFuZSBhbmQgdGhlIGNsb3Nlc3QgdHJhaW5pbmcgb2JzZXJ2YXRpb25zKSwgc28gd2Ugc2VsZWN0IHZhbHVlcyBmb3IgdGhlIHBhcmFtZXRlcnMgJFxiZXRhXzAsIFxiZXRhXzEsIFxkb3RzLCBcYmV0YV9wJCB0byBtYXhpbWl6ZSAkTSQ7IHRoYXQgaXMsIG9idGFpbiB0aGUgbGFyZ2VzdCBhbW91bnQgb2YgY3VzaGlvbiBwb3NzaWJsZSBnaXZlbiB0aGUgdHJhaW5pbmcgb2JzZXJ2YXRpb25zLgoKIyMjIE5vbi1zZXBhcmFibGUgY2FzZXMKClVuZm9ydHVuYXRlbHkgdGhlIG1heGltYWwgbWFyZ2luIGNsYXNzaWZpZXIgb25seSB3b3JrcyBpZiB0aGVyZSBleGlzdHMgYSBzZXBhcmF0aW5nIGh5cGVycGxhbmUgZm9yIHRoZSBkYXRhLiBJZiB0aGUgY2FzZXMgY2Fubm90IGJlIHBlcmZlY3RseSBzZXBhcmF0ZWQgYnkgYSBoeXBlcnBsYW5lLCB0aGVuIHdlIGNhbiBuZXZlciBzYXRpc2Z5IHRoZSBjb25kaXRpb25zIG9mIHRoZSBtYXhpbWFsIG1hcmdpbiBjbGFzc2lmaWVyLgoKYGBge3Igc2ltLW5vc2VwfQpkYXRhX2ZyYW1lKHgxID0gcnVuaWYoMjAsIC0yLCAyKSwKICAgICAgICAgICB4MiA9IHJ1bmlmKDIwLCAtMiwgMiksCiAgICAgICAgICAgeSA9IGMocmVwKC0xLCAxMCksIHJlcCgxLCAxMCkpKSAlPiUKICBtdXRhdGUoeSA9IGZhY3Rvcih5LCBsZXZlbHMgPSBjKC0xLCAxKSkpICU+JQogIGdncGxvdChhZXMoeDEsIHgyLCBjb2xvciA9IHkpKSArCiAgZ2VvbV9wb2ludCgpICsKICBsYWJzKHRpdGxlID0gIk5vbi1zZXBhcmFibGUgZGF0YSIpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCmBgYAoKIyBTdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyCgoqKlN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXJzKiogcmVsYXggdGhlIHJlcXVpcmVtZW50IG9mIHRoZSBtYXhpbWFsIG1hcmdpbiBjbGFzc2lmaWVyIGJ5IGFsbG93aW5nIHRoZSBzZXBhcmF0aW5nIGh5cGVycGxhbmUgdG8gbm90ICoqcGVyZmVjdGx5Kiogc2VwYXJhdGUgdGhlIG9ic2VydmF0aW9uczsgaW5zdGVhZCwgaXQgY2FuIG1ha2Ugc29tZSBlcnJvcnMuIFRoaXMgaXMgcmVhc29uYWJsZSB3aGVuOgoKMS4gVGhlcmUgZXhpc3RzIG5vIHBlcmZlY3RseSBzZXBhcmF0aW5nIGh5cGVycGxhbmUKMS4gQSBwZXJmZWN0bHkgc2VwYXJhdGluZyBoeXBlcnBsYW5lIGlzIHRvbyBzZW5zaXRpdmUgdG8gaW5kaXZpZHVhbCB0cmFpbmluZyBvYnNlcnZhdGlvbnMsIGdlbmVyYXRpbmcgcG90ZW50aWFsbHkgdmVyeSBzbWFsbCBtYXJnaW5zIG9yIG92ZXJmaXR0aW5nIHRoZSB0cmFpbmluZyBzZXQuXltSZW1lbWJlciB0aGF0IHdlIGNhbiB1c2UgdGhlIHBlcnBlbmRpY3VsYXIgZGlzdGFuY2UgZnJvbSB0aGUgaHlwZXJwbGFuZSBhcyBhIG1lYXN1cmUgb2YgY29uZmlkZW5jZSBpbiBvdXIgcHJlZGljdGlvbnMsIHNvIHRoZSBuZXcgdHJhaW5pbmcgb2JzZXJ2YXRpb24gZGltaW5pc2hlcyBvdXIgY29uZmlkZW5jZSBmb3IgcXVpdGUgYSBmZXcgb2YgdGhlIHJlZCB0cmFpbmluZyBvYnNlcnZhdGlvbnMuXQoKYGBge3Igc2ltLXNlbnNpdGl2ZX0KIyBvcmlnaW5hbCBtb2RlbApzZW5zaXRpdmUgPC0gZGF0YV9mcmFtZSh4MSA9IHJ1bmlmKDIwLCAtMiwgMiksCiAgICAgICAgICAgICAgICAgIHgyID0gcnVuaWYoMjAsIC0yLCAyKSwKICAgICAgICAgICAgICAgICAgeSA9IGlmZWxzZSgxICsgMiAqIHgxICsgMyAqIHgyIDwgMCwgLTEsIDEpKSAlPiUKICBtdXRhdGVfZWFjaChmdW5zKGlmZWxzZSh5ID09IDEsIC4gKyAuNSwgLikpLCB4MikgJT4lCiAgbXV0YXRlKHkgPSBmYWN0b3IoeSwgbGV2ZWxzID0gYygtMSwgMSkpKQoKc2Vuc19tb2QgPC0gc3ZtKHkgfiB4MSArIHgyLCBkYXRhID0gc2Vuc2l0aXZlLCBrZXJuZWwgPSAibGluZWFyIiwKICAgICAgICAgICAgICAgIGNvc3QgPSAxZTA1LCBzY2FsZSA9IEZBTFNFKQpzZW5zX2NvZWYgPC0gYyhzZW5zX21vZCRyaG8sIHQoc2Vuc19tb2QkY29lZnMpICUqJSBzZW5zX21vZCRTVikKc2Vuc19wbGFuZSA8LSBkYXRhX2ZyYW1lKHgxID0gc2VxKC0yLCAyLCBsZW5ndGgub3V0ID0gMTAwKSwKICAgICAgICAgICAgICAgICAgICAgICAgeDIgPSAoc2Vuc19jb2VmW1sxXV0gLSBzZW5zX2NvZWZbWzJdXSAqIHgxKSAvIHNlbnNfY29lZltbM11dKQoKZ2dwbG90KHNlbnNpdGl2ZSwgYWVzKHgxKSkgKwogIGdlb21fcG9pbnQoYWVzKHkgPSB4MiwgY29sb3IgPSB5KSkgKwogIGdlb21fbGluZShkYXRhID0gc2Vuc19wbGFuZSwgYWVzKHgxLCB4MikpICsKICBsYWJzKHRpdGxlID0gIk1heGltYWwgbWFyZ2luIGNsYXNzaWZpY2F0aW9uIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKCiMgc2xpZ2h0IHR3ZWFrCnNlbnNpdGl2ZTIgPC0gZGF0YV9mcmFtZSh4MSA9IHdpdGgoc2Vuc2l0aXZlLCB4MVt3aGljaCh4MiA9PSBtYXgoeDJbeSA9PSAtMV0pKV0pLAogICAgICAgICAgICAgICAgICAgICAgICAgeDIgPSB3aXRoKHNlbnNpdGl2ZSwgbWF4KHgyW3kgPT0gLTFdKSkgKyAuMSwKICAgICAgICAgICAgICAgICAgICAgICAgIHkgPSBmYWN0b3IoMSwgbGV2ZWxzID0gYygtMSwgMSkpKSAlPiUKICBiaW5kX3Jvd3Moc2Vuc2l0aXZlKQoKc2VuczJfbW9kIDwtIHN2bSh5IH4geDEgKyB4MiwgZGF0YSA9IHNlbnNpdGl2ZTIsIGtlcm5lbCA9ICJsaW5lYXIiLAogICAgICAgICAgICAgICAgY29zdCA9IDFlMDUsIHNjYWxlID0gRkFMU0UpCnNlbnMyX2NvZWYgPC0gYyhzZW5zMl9tb2QkcmhvLCB0KHNlbnMyX21vZCRjb2VmcykgJSolIHNlbnMyX21vZCRTVikKc2VuczJfcGxhbmUgPC0gZGF0YV9mcmFtZSh4MSA9IHNlcSgtMiwgMiwgbGVuZ3RoLm91dCA9IDEwMCksCiAgICAgICAgICAgICAgICAgICAgICAgIHgyID0gKHNlbnMyX2NvZWZbWzFdXSAtIHNlbnMyX2NvZWZbWzJdXSAqIHgxKSAvIHNlbnMyX2NvZWZbWzNdXSkKCmdncGxvdChzZW5zaXRpdmUyLCBhZXMoeDEpKSArCiAgZ2VvbV9wb2ludChhZXMoeSA9IHgyLCBjb2xvciA9IHkpKSArCiAgZ2VvbV9saW5lKGRhdGEgPSBzZW5zMl9wbGFuZSwgYWVzKHgxLCB4MikpICsKICBnZW9tX2xpbmUoZGF0YSA9IHNlbnNfcGxhbmUsIGFlcyh4MSwgeDIpLCBsaW5ldHlwZSA9IDIpICsKICBsYWJzKHRpdGxlID0gIk1heGltYWwgbWFyZ2luIGNsYXNzaWZpY2F0aW9uIikgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKYGBgCgpJbnN0ZWFkLCB3ZSB3YW50IGEgc2VwYXJhdGluZyBoeXBlcnBsYW5lIHRoYXQgZG9lcyBub3QgcGVyZmVjdGx5IHNlcGFyYXRlIHRoZSB0d28gY2xhc3NlcyBidXQgcHJvdmlkZXMgZ3JlYXRlciByb2J1c3RuZXNzIHRvIGluZGl2aWR1YWwgb2JzZXJ2YXRpb25zIGFuZCBiZXR0ZXIgY2xhc3NpZmljYXRpb24gb2YgKiptb3N0KiogdHJhaW5pbmcgb2JzZXJ2YXRpb25zLiBXZSBhcmUgd2lsbGluZyB0byBzYWNyaWZpY2UgYWNjdXJhY3kgb24gYSBmZXcgb2JzZXJ2YXRpb25zIGlmIHRoZSByZXN1bHRpbmcgaHlwZXJwbGFuZSBwZXJmb3JtcyBiZXR0ZXIgYWNyb3NzIHRoZSByZW1haW5pbmcgb2JzZXJ2YXRpb25zLgoKVGhpcyBhcHByb2FjaCBpcyBjYWxsZWQgdGhlICoqc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllcioqLiBJdCBhbGxvd3Mgb2JzZXJ2YXRpb25zIHRvIG5vdCBvbmx5IGV4aXN0IG9uIHRoZSB3cm9uZyBzaWRlIG9mIHRoZSBtYXJnaW4gKGkuZS4gaW5zaWRlIHRoZSBjdXNoaW9uIGRlZmluZWQgYnkgJE0kKSwgYnV0IGFsc28gZXhpc3Qgb24gdGhlIHdyb25nIHNpZGUgb2YgdGhlIGh5cGVycGxhbmUuCgpUaGUgYXBwcm9hY2ggaXMgdGhlIHNhbWUgYXMgdGhlIG1heGltYWwgbWFyZ2luIGNsYXNzaWZpZXIgYnV0IHRoZSBvcHRpbWl6YXRpb24gcHJvYmxlbSBpcyBzbGlnaHRseSBkaWZmZXJlbnQ6CgokJFxiZWdpbnthbGlnbmVkfQomIFx1bmRlcnNldHtcYmV0YV8wLCBcYmV0YV8xLCBcZG90cywgXGJldGFfcCwgXGVwc2lsb25fMSwgXGRvdHMsIFxlcHNpbG9uX259e1x0ZXh0e21heGltaXplfX0gJiAmIE0gXFwKJiBcdGV4dHtzLnQufSAmICYgIFxzdW1fe2o9MX1ecCBcYmV0YV9qXjIgPSAxLCBcXAomICYgJiB5X2koXGJldGFfMCArIFxiZXRhXzEgeF97aTF9ICsgXGJldGFfMiB4X3tpMn0gKyBcZG90cyArIFxiZXRhX3AgeF97aXB9KSBcZ2VxIE0oMSAtIFxlcHNpbG9uX2kpLCBcXAomICYgJiBcZXBzaWxvbl9pIFxnZXEgMCwgXHN1bV97aSA9IDF9Xm4gXGVwc2lsb25faSBcbGVxIEMgXFwKXGVuZHthbGlnbmVkfSQkCgpBcyBpbiB0aGUgbWF4aW1hbCBtYXJnaW4gY2xhc3NpZmllciwgd2UgYXR0ZW1wdCB0byBvcHRpbWl6ZSAkTSQgdG8gZ2VuZXJhdGUgdGhlIGxhcmdlc3QgcG9zc2libGUgbWFyZ2luLiBIb3dldmVyIG5vdyB3ZSBhbGxvdyBzb21lIGVycm9yICRcZXBzaWxvbl9pJCBmb3IgZWFjaCBvYnNlcnZhdGlvbiBzbyB0aGF0IHRoZXkgY2FuIGZhbGwgb24gdGhlIHdyb25nIHNpZGUgb2YgdGhlIG1hcmdpbiBvciBoeXBlcnBsYW5lLgoKKiBJZiAkXGVwc2lsb25faSA9IDAkLCB0aGVuIHRoZSAkaSR0aCBvYnNlcnZhdGlvbiBmYWxscyBvbiB0aGUgY29ycmVjdCBzaWRlIG9mIHRoZSBtYXJnaW4uCiogSWYgJFxlcHNpbG9uX2kgPiAwJCwgdGhlbiB0aGUgJGkkdGggb2JzZXJ2YXRpb24gZmFsbHMgb24gdGhlIHdyb25nIHNpZGUgb2YgdGhlIG1hcmdpbi4KKiBJZiAkXGVwc2lsb25faSA+IDEkLCB0aGVuIHRoZSAkaSR0aCBvYnNlcnZhdGlvbiBmYWxscyBvbiB0aGUgd3Jvbmcgc2lkZSBvZiB0aGUgaHlwZXJwbGFuZS4KCiRDJCBkZWZpbmVzIHByZWNpc2VseSBob3cgbXVjaCBlcnJvciB3ZSBhcmUgd2lsbGluZyB0byB0b2xlcmF0ZSBpbiB0aGUgcmVzdWx0aW5nIHNlcGFyYXRpbmcgaHlwZXJwbGFuZS4gVGhlIHN1bSBvZiB0aGUgZXJyb3JzIGZvciBhbGwgdHJhaW5pbmcgb2JzZXJ2YXRpb25zIGNhbm5vdCBleGNlZWQgJEMkLiBMYXJnZXIgdmFsdWVzIG9mICRDJCBwZXJtaXQgbW9yZSBvdmVyYWxsIGVycm9yIGluIHRoZSBzZXBhcmF0aW5nIGh5cGVycGxhbmUgYW5kIGxlYWQgdG8gbGFyZ2VyIG1hcmdpbnMsIGFuZCBzbWFsbGVyIHZhbHVlcyBvZiAkQyQgdG9sZXJhdGUgbGVzcyBlcnJvciBhbmQgcHJvZHVjZSBzbWFsbGVyIG1hcmdpbnMuIElmICRDID0gMCQgdGhlbiB3ZSBkbyBub3QgdG9sZXJhdGUgYW55IGVycm9yIGluIHRoZSBzZXBhcmF0aW5nIGh5cGVycGxhbmUsIGluIHdoaWNoIGNhc2UgJFxlcHNpbG9uXzEsIFxkb3RzLCBcZXBzaWxvbl9uID0gMCQgYW5kIHdlIGVzdGltYXRlIHRoZSBtYXhpbWFsIG1hcmdpbiBjbGFzc2lmaWVyIChvZiBjb3Vyc2UgdGhpcyBpcyBvbmx5IHBvc3NpYmxlIGlmIHRoZSBjbGFzc2VzIGFyZSBwZXJmZWN0bHkgc2VwYXJhYmxlKS4gT25jZSB3ZSBzb2x2ZSB0aGUgb3B0aW1pemF0aW9uIHByb2JsZW0sIHdlIGdlbmVyYXRlIHByZWRpY3Rpb25zIHRoZSBzYW1lIHdheSBhcyBmb3IgbWF4aW1hbCBtYXJnaW4gY2xhc3NpZmllcnMsIGJhc2VkIG9uICRmKHheKikgPSBcYmV0YV8wICsgXGJldGFfMSB4XzFeKiArIFxkb3RzICsgXGJldGFfcCB4X3BeKiQuCgpTZWxlY3RpbmcgYSB2YWx1ZSBmb3IgJEMkIGlzIHRyaWNreSBhbmQgZ2VuZXJhbGx5IGRldGVybWluZWQgdGhyb3VnaCBhIGNyb3NzLXZhbGlkYXRpb24gYXBwcm9hY2ggdG8gY29tcGFyZSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVycyB1bmRlciBkaWZmZXJlbnQgdmFsdWVzIGZvciAkQyQuIFdoZW4gJEMkIGlzIHNtYWxsLCB3ZSBnZW5lcmF0ZSBhIG1vZGVsIHdpdGggbG93LWJpYXMgKGl0IGZpdHMgdGhlIGRhdGEgd2VsbCkgYnV0IGhpZ2gtdmFyaWFuY2UgKHNtYWxsIGNoYW5nZXMgaW4gdGhlIHRyYWluaW5nIG9ic2VydmF0aW9ucyBjYW4gZ2VuZXJhdGUgc3Vic3RhbnRpYWwgY2hhbmdlcyBpbiB0aGUgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllcikuIElmICRDJCBpcyBsYXJnZSwgd2UgZ2VuZXJhdGUgYSBtb2RlbCB3aXRoIG1vcmUgYmlhcyBidXQgbGVzcyB2YXJpYW5jZS4KClRoZSBpbXBvcnRhbnQgdGhpbmcgdG8gcmVhbGl6ZSBpcyB0aGF0IHRoZSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIGlzIHJvYnVzdCwgbGlrZSB0aGUgbWF4aW1hbCBtYXJnaW4gY2xhc3NpZmllciwgdG8gY2hhbmdlcyBpbiBvYnNlcnZhdGlvbnMgb3V0c2lkZSBvZiB0aGUgbWFyZ2luLiBPYnNlcnZhdGlvbnMgdGhhdCBsaWUgZGlyZWN0bHkgb24gdGhlIG1hcmdpbiBvciBpbnNpZGUgdGhlIG1hcmdpbiBidXQgb24gdGhlIGNvcnJlY3Qgc2lkZSBvZiB0aGUgaHlwZXJwbGFuZSBhcmUgKipzdXBwb3J0IHZlY3RvcnMqKi4gVGhlIHN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXIgd2lsbCBvbmx5IGNoYW5nZSBpZiB0aG9zZSBvYnNlcnZhdGlvbnMgYXJlIGFkanVzdGVkLiBXaGVuICRDJCBpcyBsYXJnZSwgdGhlIG51bWJlciBvZiBvYnNlcnZhdGlvbnMgZmFsbGluZyBpbnNpZGUgdGhlIG1hcmdpbiBpbmNyZWFzZXMgYW5kIHRoZXJlZm9yZSB0aGUgbnVtYmVyIG9mIHN1cHBvcnQgdmVjdG9ycyBhbHNvIGluY3JlYXNlcy4KCmBgYHtyIHNpbS1jLCBmaWcuYXNwPTF9CnNpbV9jIDwtIGRhdGFfZnJhbWUoeDEgPSBybm9ybSgyMCksCiAgICAgICAgICAgICAgICAgICAgeDIgPSBybm9ybSgyMCksCiAgICAgICAgICAgICAgICAgICAgeSA9IGlmZWxzZSgyICogeDEgKyB4MiArIHJub3JtKDIwLCAwLCAuMjUpIDwgMCwgLTEsIDEpKSAlPiUKICBtdXRhdGUoeSA9IGZhY3Rvcih5LCBsZXZlbHMgPSBjKC0xLCAxKSkpCgpwbG90X3N2bSA8LSBmdW5jdGlvbihkZiwgY29zdCA9IDEpewogICMgZXN0aW1hdGUgbW9kZWwKICBzaW1fbW9kIDwtIHN2bSh5IH4geDEgKyB4MiwgZGF0YSA9IGRmLCBrZXJuZWwgPSAibGluZWFyIiwKICAgICAgICAgICAgICAgICBjb3N0ID0gY29zdCwKICAgICAgICAgICAgICAgICBzY2FsZSA9IEZBTFNFKQogIAogICMgZXh0cmFjdCBzZXBhcmF0aW5nIGh5cGVycGxhbmUKICBzaW1fY29lZiA8LSBjKHNpbV9tb2QkcmhvLCB0KHNpbV9tb2QkY29lZnMpICUqJSBzaW1fbW9kJFNWKQogIHNpbV9wbGFuZSA8LSBkYXRhX2ZyYW1lKHgxID0gc2VxKG1pbihkZiR4MSksIG1heChkZiR4MSksIGxlbmd0aC5vdXQgPSAxMDApLAogICAgICAgICAgICAgICAgICAgICAgICAgIHgyID0gKC1zaW1fY29lZltbMV1dIC0gc2ltX2NvZWZbWzJdXSAqIHgxKSAvIHNpbV9jb2VmW1szXV0pCiAgCiAgIyBleHRyYWN0IHByb3BlcnRpZXMgdG8gZHJhdyBtYXJnaW5zCiAgc2ltX3ByZWQgPC0gcHJlZGljdChzaW1fbW9kLCBkZiwgZGVjaXNpb24udmFsdWVzID0gVFJVRSkKICBzaW1fZGlzdCA8LSBhdHRyKHNpbV9wcmVkLCAiZGVjaXNpb24udmFsdWVzIikKICAKICBnZ3Bsb3QoZGYsIGFlcyh4MSkpICsKICAgIGdlb21fcG9pbnQoYWVzKHkgPSB4MiwgY29sb3IgPSB5KSkgKwogICAgZ2VvbV9saW5lKGRhdGEgPSBzaW1fcGxhbmUsIGFlcyh4MSwgeDIpKSArCiAgICBnZW9tX2xpbmUoZGF0YSA9IG11dGF0ZShzaW1fcGxhbmUsIHgyID0geDIgLSBtaW4oYWJzKHNpbV9kaXN0KSkpLAogICAgICAgICAgICAgIGFlcyh4MSwgeDIpLCBsaW5ldHlwZSA9IDIpICsKICAgIGdlb21fbGluZShkYXRhID0gbXV0YXRlKHNpbV9wbGFuZSwgeDIgPSB4MiArIG1pbihhYnMoc2ltX2Rpc3QpKSksCiAgICAgICAgICAgICAgYWVzKHgxLCB4MiksIGxpbmV0eXBlID0gMikgKwogICAgbGFicyhzdWJ0aXRsZSA9IHN0cl9jKCJDb3N0ID0gIiwgY29zdCkpICsKICAgIGNvb3JkX2VxdWFsKHhsaW0gPSByYW5nZShkZiR4MSksCiAgICAgICAgICAgICAgICAgICAgeWxpbSA9IHJhbmdlKGRmJHgyKSkgKwogICAgdGhlbWUobGVnZW5kLnBvc2l0aW9uID0gIm5vbmUiKQp9CgpncmlkLmFycmFuZ2UoZ3JvYnMgPSBsaXN0KHBsb3Rfc3ZtKHNpbV9jLCBjb3N0ID0gMSksCiAgICAgICAgICAgICAgICAgIHBsb3Rfc3ZtKHNpbV9jLCBjb3N0ID0gMTApLAogICAgICAgICAgICAgICAgICBwbG90X3N2bShzaW1fYywgY29zdCA9IDEwMCksCiAgICAgICAgICAgICAgICAgIHBsb3Rfc3ZtKHNpbV9jLCBjb3N0ID0gMjAwKSksIG5jb2wgPSAyKQpgYGAKCiMgU3VwcG9ydCB2ZWN0b3IgbWFjaGluZXMKCiMjIE5vbi1saW5lYXIgZGVjaXNpb24gYm91bmRhcmllcwoKU28gZmFyIHdlIGhhdmUgb25seSBkZW1vbnN0cmF0ZWQgdGhlIHN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXIgd2l0aCBhICoqbGluZWFyIGRlY2lzaW9uIGJvdW5kYXJ5KiouIEJ1dCBhcyB3aXRoIGxpbmVhciByZWdyZXNzaW9uLCB3ZSBhbHNvIGtub3cgdGhlcmUgYXJlIFttZXRob2RzIG9mIGV4dGVuZGluZyB0aGUgbGluZWFyIGZyYW1ld29yayB0byBhY2NvdW50IGZvciBub24tbGluZWFyIHJlbGF0aW9uc2hpcHNdKHBlcnNwMDA3X25vbmxpbmVhci5odG1sKS4gQ29uc2lkZXIgdGhlIGZvbGxvd2luZyByZWxhdGlvbnNoaXA6CgpgYGB7ciBzaW0tbm9ubGluZWFyfQpzZXQuc2VlZCgxKQp4IDwtIG1hdHJpeChybm9ybSgyMDAgKiAyKSwgbmNvbCA9IDIpCnhbMToxMDAsIF0gPC0geFsxOjEwMCwgXSArIDIKeFsxMDE6MTUwLCBdIDwtIHhbMTAxOjE1MCwgXSAtIDIKeSA8LSBjKHJlcCgxLCAxNTApLCByZXAoMiwgNTApKQpzaW1fbm9ubG0gPC0gZGF0YS5mcmFtZSh4ID0geCwgeSA9IGFzLmZhY3Rvcih5KSkgJT4lCiAgYXNfdGliYmxlICU+JQogIHJlbmFtZSh4MSA9IHguMSwKICAgICAgICAgeDIgPSB4LjIpCgpyYWRpYWxfcCA8LSBnZ3Bsb3Qoc2ltX25vbmxtLCBhZXMoeDEsIHgyLCBjb2xvciA9IHkpKSArCiAgZ2VvbV9wb2ludCgpICsKICB0aGVtZShsZWdlbmQucG9zaXRpb24gPSAibm9uZSIpCnJhZGlhbF9wCmBgYAoKQSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyIHdpdGggYSBsaW5lYXIgZGVjaXNpb24gYm91bmRhcnkgd291bGQgcGVyZm9ybSB2ZXJ5IHBvb3JseSBvbiB0aGlzIGRhdGEuCgpXZSBjb3VsZCBnbyB0aGUgcm91dGUgd2UgZGlzY3Vzc2VkIGJlZm9yZSBhbmQgcmVsYXggdGhlIGxpbmVhcml0eSBhc3N1bXB0aW9uIGJ5IGFkZGluZyBxdWFkcmF0aWMgb3IgY3ViaWMgdGVybXMgdG8gYWRkcmVzcyB0aGUgbm9uLWxpbmVhcml0eS4gRm9yIGluc3RhbmNlLCBhZGRpbmcgYSBxdWFkcmF0aWMgdGVybSB3b3VsZCBjaGFuZ2UgdGhlIG9wdGltaXphdGlvbiBwcm9ibGVtIHRvIHVzaW5nICQycCQgZmVhdHVyZXM6CgokJFhfMSwgWF8xXjIsIFhfMiwgWF8yXjIsIFxkb3RzLCBYX3AsIFhfcF4yJCQKCkFuZCB0aGVyZWZvcmUgdGhlIG9wdGltaXphdGlvbiBwcm9ibGVtIGJlY29tZXM6CgokJFxiZWdpbnthbGlnbmVkfQomIFx1bmRlcnNldHtcYmV0YV8wLCBcYmV0YV97MTF9LCBcYmV0YV97MTJ9LCBcZG90cywgXGJldGFfe3AxfSwgXGJldGFfe3AyfSwgXGVwc2lsb25fMSwgXGRvdHMsIFxlcHNpbG9uX259e1x0ZXh0e21heGltaXplfX0gJiAmIE0gXFwKJiBcdGV4dHtzLnQufSAmICYgeV9pIFxsZWZ0KCBcYmV0YV8wICsgXHN1bV97aiA9IDF9XnAgXGJldGFfe2oxfSB4X3tpan0gKyBcc3VtX3tqID0gMX1ecCBcYmV0YV97ajJ9IHhfe2lqfV4yIFxyaWdodCkgXGdlcSBNKDEgLSBcZXBzaWxvbl9pKSwgXFwKJiAmICYgXGVwc2lsb25faSBcZ2VxIDAsIFxzdW1fe2kgPSAxfV5uIFxlcHNpbG9uX2kgXGxlcSBDLCBcc3VtX3tqID0gMX1ecCBcc3VtX3trID0gMX1eMiBcYmV0YV97amt9XjIgPSAxIFxcClxlbmR7YWxpZ25lZH0kJAoKVGhlIHByb2JsZW0gd2l0aCB0aGlzIGFwcHJvYWNoIGlzIHRoYXQgYXMgeW91IGFkZCBwb2x5bm9taWFsIHRlcm1zIChvciBpbnRlcmFjdGlvbnMgb3Igc3BsaW5lcykgeW91IGluY3JlYXNlIHRoZSAqKmZlYXR1cmUgc3BhY2UqKiB1c2VkIHRvIGdlbmVyYXRlIHRoZSBkZWNpc2lvbiBib3VuZGFyeSBhbmQgdGhlIHNlcGFyYXRpbmcgaHlwZXJwbGFuZSAoaS5lLiB0aGUgdG90YWwgbnVtYmVyIG9mIHByZWRpY3RvcnMgaW5jcmVhc2VzKS4gTWF4aW1pemluZyB0aGlzIG9wdGltaXphdGlvbiBwcm9ibGVtIGlzIGFscmVhZHkgY29tcHV0YXRpb25hbGx5IGludGVuc2l2ZTogaWYgeW91IGNvbnRpbnVlIHRvIGluY3JlYXNlIHRoZSBudW1iZXIgb2YgZmVhdHVyZXMsIGNvbXB1dGluZyB0aGUgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciBiZWNvbWVzIG11Y2ggbW9yZSBkaWZmaWN1bHQgYW5kIGluZWZmaWNpZW50LCBhbmQgbWF5IGV2ZW4gYmVjb21lIGltcG9zc2libGUuCgojIyBTdXBwb3J0IHZlY3RvciBtYWNoaW5lcwoKVGhlICoqc3VwcG9ydCB2ZWN0b3IgbWFjaGluZSoqIGlzIGFuIGV4dGVuc2lvbiBvZiB0aGUgc3VwcG9ydCB2ZWN0b3IgY2xhc3NpZmllciB0aGF0IGVubGFyZ2VzIHRoZSBmZWF0dXJlIHNwYWNlIGJ5IHVzaW5nICoqa2VybmVscyoqLiBLZXJuZWxzIGFyZSBhIGNvbXB1dGF0aW9uYWxseSBlZmZpY2llbnQgbWV0aG9kIGZvciBleHRlbmRpbmcgdGhlIGZlYXR1cmUgc3BhY2UgdG8gYWNjb21vZGF0ZSBhIG5vbi1saW5lYXIgZGVjaXNpb24gYm91bmRhcnkuCgpDb21wdXRpbmcgdGhlIHN1cHBvcnQgdmVjdG9yIGNsYXNzaWZpZXIgaW52b2x2ZXMgdGhlICoqaW5uZXIgcHJvZHVjdHMqKiBvZiB0aGUgb2JzZXJ2YXRpb25zLCByYXRoZXIgdGhhbiB0aGUgb2JzZXJ2YXRpb25zIHRoZW1zZWx2ZXMuXltMaWtlIGhvdyBib29zdGluZyB1c2VzIHRoZSByZXNpZHVhbHMgb2YgdGhlIHJlc3BvbnNlIHZhcmlhYmxlICRZJCwgcmF0aGVyIHRoYW4gJFkkIGl0c2VsZi5dIFRoZSBpbm5lciBwcm9kdWN0IG9mIHR3byAkciQtbGVuZ3RoIHZlY3RvcnMgJGEkIGFuZCAkYiQgaXMgZGVmaW5lZCBhcyAkXGxhbmdsZSBhLGIgXHJhbmdsZSA9IFxzdW1fe2kgPSAxfV5yIGFfaSBiX2kkLgoKYGBge3IgaW5uZXItcHJvZH0KKHggPC0gMTo1KQooeSA8LSAxOjUpCgp4ICUqJSB5CmBgYAoKU28gdGhlIGlubmVyIHByb2R1Y3Qgb2YgdHdvIG9ic2VydmF0aW9ucyBpczoKCiQkXGxhbmdsZSB4X2ksIHhfe2knfSBccmFuZ2xlID0gXHN1bV97aiA9IDF9XnAgeF97aWp9IHhfe2knan0kJAoKVGhlIGxpbmVhciBzdXBwb3J0IHZlY3RvciBjYW4gYmUgd3JpdHRlbiBhczoKCiQkZih4KSA9IFxiZXRhXzAgKyBcc3VtX3tpID0gMX1ebiBcYWxwaGFfaSBcbGFuZ2xlIHgsIHhfaSBccmFuZ2xlJCQKCndoZXJlIHRoZXJlIGFyZSAkbiQgcGFyYW1ldGVycyAkXGFscGhhX2ksIGkgPSAxLCBcZG90cywgbiQsIG9uZSBwZXIgdHJhaW5pbmcgb2JzZXJ2YXRpb24uIFRvIGVzdGltYXRlIHRoZSBwYXJhbWV0ZXJzICRcYWxwaGFfMSwgXGRvdHMsIFxhbHBoYV9uLCBcYmV0YV8wJCwgd2UganVzdCBuZWVkIHRvIGNhbGN1bGF0ZSB0aGUgaW5uZXIgcHJvZHVjdHMgYmV0d2VlbiBhbGwgcGFpcnMgb2YgdHJhaW5pbmcgb2JzZXJ2YXRpb25zLiBIb3dldmVyIGZvciBvYnNlcnZhdGlvbnMgd2hpY2ggYXJlIG5vdCBhbHNvIHN1cHBvcnQgdmVjdG9ycywgJFxhbHBoYV9pJCBpcyBhY3R1YWxseSB6ZXJvLiBTbyBpbiBmYWN0LCB3ZSBvbmx5IG5lZWQgdG8gY2FsY3VsYXRlIHRoZSBpbm5lciBwcm9kdWN0cyBmb3Igc3VwcG9ydCB2ZWN0b3JzICRcbWF0aGJie1N9JCB3aGljaCByZWR1Y2VzIHRoZSBjb21wbGV4aXR5IG9mIHRoaXMgdGFzazoKCiQkZih4KSA9IFxiZXRhXzAgKyBcc3VtX3tpIFxpbiBcbWF0aGJie1N9fSBcYWxwaGFfaSBcbGFuZ2xlIHgsIHhfaSBccmFuZ2xlJCQKCiMjIyBLZXJuZWxzCgpOb3cgcmF0aGVyIHRoYW4gdXNpbmcgdGhlIGFjdHVhbCBpbm5lciBwcm9kdWN0LAoKJCRcbGFuZ2xlIHhfaSwgeF97aSd9IFxyYW5nbGUgPSBcc3VtX3tqID0gMX1ecCB4X3tpan0geF97aSdqfSQkCgppbnN0ZWFkIHdlIGNhbiB1c2UgYSAqKmdlbmVyYWxpemF0aW9uKiogb2YgdGhlIGlubmVyIHByb2R1Y3QgZm9sbG93aW5nIHNvbWUgZnVuY3Rpb25hbCBmb3JtICRLJCB3aGljaCB3ZSB3aWxsIGNhbGwgYSBrZXJuZWw6CgokJEsoeF9pLCB4X3tpJ30pJCQKCkEga2VybmVsIGNhbGN1bGF0ZXMgdGhlIHNpbWlsYXJpdHkgb2YgdHdvIG9ic2VydmF0aW9ucy4gRm9yIGV4YW1wbGUsCgokJEsoeF9pLCB4X3tpJ30pID0gXHN1bV97aiA9IDF9XnAgeF97aWp9IHhfe2knan0kJAoKZ2VuZXJhdGVzIHRoZSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyLCBhbHNvIGtub3duIGFzIHRoZSAqKmxpbmVhciBrZXJuZWwqKi4gQWx0ZXJuYXRpdmVseSwgd2UgY291bGQgdXNlIGEgZGlmZmVyZW50IGtlcm5lbCBmdW5jdGlvbiBzdWNoIGFzOgoKJCRLKHhfaSwgeF97aSd9KSA9ICgxICsgXHN1bV97aiA9IDF9XnAgeF97aWp9IHhfe2knan0pXmQkJAoKVGhpcyBpcyBjYWxsZWQgdGhlICoqcG9seW5vbWlhbCBrZXJuZWwqKiBvZiBkZWdyZWUgJGQkIHdoZXJlICRkJCBpcyBzb21lIHBvc2l0aXZlIGludGVnZXIuIFRoaXMgd2lsbCBnZW5lcmF0ZSBhIG11Y2ggbW9yZSBmbGV4aWJsZSBkZWNpc2lvbiBib3VuZGFyeSwgc2ltaWxhciB0byBob3cgdXNpbmcgYSBzcGxpbmUgaW4gbGluZWFyIHJlZ3Jlc3Npb24gZ2VuZXJhdGVzIGEgZmxleGlibGUsIG5vbi1saW5lYXIgZnVuY3Rpb25hbCBmb3JtLiBUbyB1c2UgdGhpcyBrZXJuZWwgaW4gYSBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyLCB0aGUgZnVuY3Rpb25hbCBmb3JtIGJlY29tZXM6CgokJGYoeCkgPSBcYmV0YV8wICsgXHN1bV97aSBcaW4gXG1hdGhiYntTfX0gXGFscGhhX2kgSyh4LHhfaSkkJAoKYGBge3Igc3ZtLXBvbHl9CnNpbV9ub25sbSA8LSBkYXRhX2ZyYW1lKHgxID0gcnVuaWYoMTAwLCAtMiwgMiksCiAgICAgICAgICAgICAgICAgIHgyID0gcnVuaWYoMTAwLCAtMiwgMiksCiAgICAgICAgICAgICAgICAgIHkgPSBpZmVsc2UoeDEgKyB4MV4yICsgeDFeMyAtIHgyIDwgMCArCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBybm9ybSgxMDAsIDAsIDEpLCAtMSwgMSkpICU+JQogIG11dGF0ZSh5ID0gZmFjdG9yKHksIGxldmVscyA9IGMoLTEsIDEpKSkKCmdncGxvdChzaW1fbm9ubG0sIGFlcyh4MSwgeDIsIGNvbG9yID0geSkpICsKICBnZW9tX3BvaW50KCkgKwogIHRoZW1lKGxlZ2VuZC5wb3NpdGlvbiA9ICJub25lIikKCnN2bSh5IH4geDEgKyB4MiwgZGF0YSA9IHNpbV9ub25sbSwga2VybmVsID0gInBvbHlub21pYWwiLCBzY2FsZSA9IEZBTFNFLCBjb3N0ID0gMSkgJT4lCiAgcGxvdChzaW1fbm9ubG0sIHgyIH4geDEpCmBgYAoKQW5vdGhlciBjaG9pY2UgaXMgdGhlICoqcmFkaWFsIGtlcm5lbCoqOgoKJCRLKHhfaSwgeF97aSd9KSA9IFxleHAoLSBcZ2FtbWEgXHN1bV97aj0xfV5wICh4X3tpan0gLSB4X3tpJ2p9KV4yKSQkCgp3aGVyZSAkXGdhbW1hJCBpcyBzb21lIHBvc2l0aXZlIGNvbnN0YW50LiBSYWRpYWwga2VybmVscyB3b3JrIGJ5IGxvY2FsaXppbmcgcHJlZGljdGlvbnMgZm9yIHRlc3Qgb2JzZXJ2YXRpb25zIGJhc2VkIG9uIHRoZWlyIEV1Y2xpZGlhbiBkaXN0YW5jZSB0byBuZWFyYnkgdHJhaW5pbmcgb2JzZXJ2YXRpb25zLgoKYGBge3Igc3ZtLXJhZGlhbH0Kc2ltX3JhZF9tb2QgPC0gc3ZtKHkgfiB4MSArIHgyLCBkYXRhID0gc2ltX25vbmxtLAogICAgICAgICAgICAgICAgICAgICBrZXJuZWwgPSAicmFkaWFsIiwgY29zdCA9IDUsIHNjYWxlID0gRkFMU0UpCgpyYWRpYWxfcApwbG90KHNpbV9yYWRfbW9kLCBzaW1fbm9ubG0sIHgyIH4geDEpCmBgYAoKS2VybmVscyBhcmUgYmV0dGVyIHRvIHVzZSBmb3Igc3VwcG9ydCB2ZWN0b3IgbWFjaGluZXMgdGhhbiBvdGhlciBub24tbGluZWFyIGFwcHJvYWNocyBiZWNhdXNlIHRoZXkgZG8gbm90IGVubGFyZ2UgdGhlIGZlYXR1cmUgc3BhY2UuIFRoYXQgaXMsIHlvdSBuZWVkIHRvIGNvbXB1dGUgJEsoeF9pLCB4X3tpJ30pJCBmb3IgYWxsICRcYmlub217bn17Mn0kIGRpc3RpbmN0IHBhaXJzICRpLCBpJyQsIGJ1dCAkcCQgaXRzZWxmIHJlbWFpbnMgdGhlIHNhbWUuICoqWW91IGRvIG5vdCBuZWVkIHRvIGV4cGxpY2l0bHkgZW5sYXJnZSB0aGUgZmVhdHVyZSBzcGFjZSB0byBhY2NvbXBsaXNoIHRoaXMgdGFzayoqLiBUaGUgdG90YWwgbnVtYmVyIG9mIGZlYXR1cmVzL3ByZWRpY3RvcnMvaW5kZXBlbmRlbnQgdmFyaWFibGVzIGluIHRoZSBtb2RlbCByZW1haW5zIHRoZSBzYW1lLCBzbyB5b3UgY2FuIG1vcmUgZWFzaWx5IGNvbXB1dGUgdGhlIFNWTS4KCiMgQXBwbHlpbmcgYW5kIGludGVycHJldGluZyBTVk1zCgpTVk1zIGFyZSBnZW5lcmFsbHkgdXNlZCBmb3IgKipwcmVkaWN0aW9uIG1vZGVscyoqLiBUaGV5IGdlbmVyYXRlIHByZWRpY3RlZCBjbGFzc2VzIGZvciB0ZXN0IG9ic2VydmF0aW9ucyBhbmQgd2UgY2FuIGFzc2VzcyBjb25maWRlbmNlIGluIHRoZSBtb2RlbCBhbmQgb3ZlcmFsbCBtb2RlbCBmaXQgdXNpbmcgc3RhbmRhcmQgbWV0cmljLiBIb3dldmVyIFNWTXMgYXJlIG5vdCBnb29kIGZvciBjb25kdWN0aW5nIGluZmVyZW5jZSwgc2luY2UgdGhlcmUgYXJlIG5vIGVhc3kgbWV0aG9kcyBmb3IgaW50ZXJwcmV0aW5nIHRoZSByZWxhdGl2ZSBpbXBvcnRhbmNlIGFuZCBpbmZsdWVuY2Ugb2YgaW5kaXZpZHVhbCBwcmVkaWN0b3JzIG9uIHRoZSBzZXBhcmF0aW5nIGh5cGVycGxhbmUuIFJlZ3Jlc3Npb24gY29lZmZpY2llbnRzIGFyZSBnZW5lcmFsbHkgZWFzeSB0byBpbnRlcnByZXQsIGFuZCBldmVuIHRyZWUtYmFzZWQgbWV0aG9kcyBoYXZlIHZpc3VhbCBhbmQgc3RhdGlzdGljYWwgaW50ZXJwcmV0YXRpb25zICh2YXJpYWJsZSBpbXBvcnRhbmNlIHBsb3RzKSBvZiB0aGUgaW5kaXZpZHVhbCBwcmVkaWN0b3JzLiBHZW5lcmFsbHkgU1ZNcyBhcmUgaW50ZXJwcmV0ZWQgYnkgYXNzZXNzaW5nIG92ZXJhbGwgbW9kZWwgZml0IGFuZCBlcnJvciByYXRlcywgdXNpbmcgYSBjb21iaW5hdGlvbiBvZiBjcm9zcy12YWxpZGF0aW9uIG1ldGhvZHMgYW5kIHZpc3VhbHMgc3VjaCBhcyBST0MgY3VydmVzLgoKIyMgVGl0YW5pYwoKTGV0J3MgdHJ5IHRoaXMgbWV0aG9kIG91dCBvbiBvdXIgdHJ1c3R5IFRpdGFuaWMgZGF0YXNldCwgdXNpbmcgYWdlIGFuZCBnZW5kZXIgdG8gcHJlZGljdCBzdXJ2aXZhbC4gRmlyc3Qgd2UnbGwgc3BsaXQgb3VyIGRhdGFzZXQgaW50byB0cmFpbmluZyBhbmQgdGVzdCBzZXRzLgoKYGBge3IgdGl0YW5pYy1kYXRhfQp0aXRhbmljIDwtIHRpdGFuaWNfdHJhaW4gJT4lCiAgYXNfdGliYmxlICU+JQogIHNlbGVjdCgtTmFtZSwgLVRpY2tldCwgLUNhYmluLCAtUGFzc2VuZ2VySWQpICU+JQogIG11dGF0ZV9lYWNoKGZ1bnMoYXMuZmFjdG9yKC4pKSwgU3Vydml2ZWQsIFBjbGFzcywgRW1iYXJrZWQpICU+JQogIG5hLm9taXQKCnRpdGFuaWNfc3BsaXQgPC0gcmVzYW1wbGVfcGFydGl0aW9uKHRpdGFuaWMsIHAgPSBjKCJ0ZXN0IiA9IC4zLCAidHJhaW4iID0gLjcpKQpgYGAKCk91ciBmaXJzdCBhdHRlbXB0IHdpbGwgdXNlIGEgbGluZWFyIGtlcm5lbCAoaS5lLiBzdXBwb3J0IHZlY3RvciBjbGFzc2lmaWVyKSBhbmQgd2UnbGwgdXNlIDEwLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiB0byBkZXRlcm1pbmUgdGhlIG9wdGltYWwgY29zdCBwYXJhbWV0ZXIgJEMkLgoKYGBge3IgdGl0YW5pYy1saW5lYXItdHVuZSwgZGVwZW5kc29uPSJ0aXRhbmljLWRhdGEifQp0aXRhbmljX3R1bmUgPC0gdHVuZShzdm0sIFN1cnZpdmVkIH4gQWdlICsgRmFyZSwgZGF0YSA9IGFzX3RpYmJsZSh0aXRhbmljX3NwbGl0JHRyYWluKSwKICAgICAgICAgICAgICAgICAgICAga2VybmVsID0gImxpbmVhciIsCiAgICAgICAgICAgICAgICAgICAgIHJhbmdlID0gbGlzdChjb3N0ID0gYyguMDAxLCAuMDEsIC4xLCAxLCA1LCAxMCwgMTAwKSkpCnN1bW1hcnkodGl0YW5pY190dW5lKQpgYGAKCiRDID0gMSQgcHJvZHVjZXMgdGhlIGxvd2VyIENWIGVycm9yIHJhdGUsIHNvIGxldCdzIHVzZSB0aGF0IG1vZGVsIGZvciBlc3RpbWF0aW5nIG1vZGVsIGZpdCB1c2luZyBhIFtST0MgY3VydmVdKHBlcnNwMDA0X2xvZ2lzdGljX3JlZ3Jlc3Npb24uaHRtbCNyZWNlaXZlcl9vcGVyYXRpbmdfY2hhcmFjdGVyaXN0aWNzXyhyb2MpX2N1cnZlKS4KCmBgYHtyIHRpdGFuaWMtbGluZWFyLXByZWR9CnRpdGFuaWNfYmVzdCA8LSB0aXRhbmljX3R1bmUkYmVzdC5tb2RlbApzdW1tYXJ5KHRpdGFuaWNfYmVzdCkKCiMgZ2V0IHByZWRpY3Rpb25zIGZvciB0ZXN0IHNldApmaXR0ZWQgPC0gcHJlZGljdCh0aXRhbmljX2Jlc3QsIGFzX3RpYmJsZSh0aXRhbmljX3NwbGl0JHRlc3QpLCBkZWNpc2lvbi52YWx1ZXMgPSBUUlVFKSAlPiUKICBhdHRyaWJ1dGVzCgpyb2NfbGluZSA8LSByb2MoYXNfdGliYmxlKHRpdGFuaWNfc3BsaXQkdGVzdCkkU3Vydml2ZWQsIGZpdHRlZCRkZWNpc2lvbi52YWx1ZXMpCnBsb3Qocm9jX2xpbmUpCmF1Yyhyb2NfbGluZSkKYGBgCgpIb3cgZG9lcyB0aGlzIGNvbXBhcmUgdG8gYSBwb2x5bm9taWFsIGtlcm5lbCBTVk0/CgpgYGB7ciB0aXRhbmljLXN2bS1wb2x5fQp0aXRhbmljX3BvbHlfdHVuZSA8LSB0dW5lKHN2bSwgU3Vydml2ZWQgfiBBZ2UgKyBGYXJlLCBkYXRhID0gYXNfdGliYmxlKHRpdGFuaWNfc3BsaXQkdHJhaW4pLAogICAgICAgICAgICAgICAgICAgICBrZXJuZWwgPSAicG9seW5vbWlhbCIsCiAgICAgICAgICAgICAgICAgICAgIHJhbmdlID0gbGlzdChjb3N0ID0gYyguMDAxLCAuMDEsIC4xLCAxLCA1LCAxMCwgMTAwKSkpCnN1bW1hcnkodGl0YW5pY19wb2x5X3R1bmUpCgp0aXRhbmljX3BvbHlfYmVzdCA8LSB0aXRhbmljX3BvbHlfdHVuZSRiZXN0Lm1vZGVsCnN1bW1hcnkodGl0YW5pY19wb2x5X2Jlc3QpCgojIGdldCBwcmVkaWN0aW9ucyBmb3IgdGVzdCBzZXQKZml0dGVkIDwtIHByZWRpY3QodGl0YW5pY19wb2x5X2Jlc3QsIGFzX3RpYmJsZSh0aXRhbmljX3NwbGl0JHRlc3QpLCBkZWNpc2lvbi52YWx1ZXMgPSBUUlVFKSAlPiUKICBhdHRyaWJ1dGVzCgpyb2NfcG9seSA8LSByb2MoYXNfdGliYmxlKHRpdGFuaWNfc3BsaXQkdGVzdCkkU3Vydml2ZWQsIGZpdHRlZCRkZWNpc2lvbi52YWx1ZXMpCnBsb3Qocm9jX3BvbHkpCmF1Yyhyb2NfcG9seSkKYGBgCgpOb3QgcXVpdGUgYXMgZ29vZC4gVGhlIG9wdGltYWwgY29zdCBwYXJhbWV0ZXIgaXMgc21hbGxlciAoJC4xJCksIGJ1dCB0aGUgYXNzb2NpYXRlZCBDViBlcnJvciByYXRlIGlzIGhpZ2hlciB0aGFuIHRoZSBsaW5lYXIga2VybmVsIGFuZCB0aGUgcmVzdWx0aW5nIHRlc3QgQVVDIGlzIHNtYWxsZXIuIEhvdyBkb2VzIHRoaXMgc3RhY2sgdXAgYWdhaW5zdCB0aGUgcmFkaWFsIGtlcm5lbD8KCmBgYHtyIHRpdGFuaWMtc3ZtLXJhZGlhbH0KdGl0YW5pY19yYWRfdHVuZSA8LSB0dW5lKHN2bSwgU3Vydml2ZWQgfiBBZ2UgKyBGYXJlLCBkYXRhID0gYXNfdGliYmxlKHRpdGFuaWNfc3BsaXQkdHJhaW4pLAogICAgICAgICAgICAgICAgICAgICBrZXJuZWwgPSAicmFkaWFsIiwKICAgICAgICAgICAgICAgICAgICAgcmFuZ2UgPSBsaXN0KGNvc3QgPSBjKC4wMDEsIC4wMSwgLjEsIDEsIDUsIDEwLCAxMDApKSkKc3VtbWFyeSh0aXRhbmljX3JhZF90dW5lKQoKdGl0YW5pY19yYWRfYmVzdCA8LSB0aXRhbmljX3JhZF90dW5lJGJlc3QubW9kZWwKc3VtbWFyeSh0aXRhbmljX3JhZF9iZXN0KQoKIyBnZXQgcHJlZGljdGlvbnMgZm9yIHRlc3Qgc2V0CmZpdHRlZCA8LSBwcmVkaWN0KHRpdGFuaWNfcmFkX2Jlc3QsIGFzX3RpYmJsZSh0aXRhbmljX3NwbGl0JHRlc3QpLCBkZWNpc2lvbi52YWx1ZXMgPSBUUlVFKSAlPiUKICBhdHRyaWJ1dGVzCgpyb2NfcmFkIDwtIHJvYyhhc190aWJibGUodGl0YW5pY19zcGxpdCR0ZXN0KSRTdXJ2aXZlZCwgZml0dGVkJGRlY2lzaW9uLnZhbHVlcykKcGxvdChyb2NfcmFkKQphdWMocm9jX3JhZCkKYGBgCgpUaGUgcmFkaWFsIGltcHJvdmVzIHVwb24gYm90aCB0aGUgcG9seW5vbWlhbCBhbmQgdGhlIGxpbmVhciBTVk1zLiBUaGUgQ1YgZXJyb3IgcmF0ZSBpcyBsb3dlciBhbmQgdGhlIHRlc3QgQVVDIGlzIGhpZ2hlci4KCkl0J3MgZWFzaWVyIHRvIGNvbXBhcmUgaWYgd2UgcGxvdCB0aGUgUk9DIGN1cnZlcyBvbiB0aGUgc2FtZSBwbG90dGluZyB3aW5kb3c6CgpgYGB7ciB0aXRhbmljLXJvYy1jb21wYXJlfQpwbG90KHJvY19saW5lLCBwcmludC5hdWMgPSBUUlVFLCBjb2wgPSAiYmx1ZSIpCnBsb3Qocm9jX3BvbHksIHByaW50LmF1YyA9IFRSVUUsIGNvbCA9ICJyZWQiLCBwcmludC5hdWMueSA9IC40LCBhZGQgPSBUUlVFKQpwbG90KHJvY19yYWQsIHByaW50LmF1YyA9IFRSVUUsIGNvbCA9ICJvcmFuZ2UiLCBwcmludC5hdWMueSA9IC4zLCBhZGQgPSBUUlVFKQpgYGAKCkJhc2VkIG9uIG91ciBwcmVkaWN0aW9ucyBmcm9tIHRoZSB0ZXN0IHNldCwgdGhlIHJhZGlhbCBTVk0gcGVyZm9ybXMgdGhlIGJlc3Qgb24gdGhlIEFVQywgZm9sbG93ZWQgYnkgdGhlIGxpbmVhciBTVk0sIGFuZCB3b3JzdCBvZiBhbGwgdGhlIHBvbHlub21pYWwgU1ZNLgoKIyMgVm90ZXIgdHVybm91dAoKTGV0J3MgdGVzdCB0aGUgU1ZNIG1ldGhvZCBvbiBvdXIgdm90ZXIgdHVybm91dCBkYXRhLiBBZ2FpbiwgbGV0J3Mgc3RhcnQgYnkgc3BsaXR0aW5nIHRoZSBkYXRhIGludG8gdHJhaW5pbmcgYW5kIHRlc3Qgc2V0cy5eW1doeSB1c2UgdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoPyBXZSd2ZSBkaXNjdXNzZWQgdGhlIFtpbmFkZXF1YWNpZXNdKHBlcnNwMDA2X3Jlc2FtcGxpbmcuaHRtbCNkcmF3YmFja3NfdG9fdGhlX3ZhbGlkYXRpb25fc2V0X2FwcHJvYWNoKSBvZiBpdCBiZWZvcmUuIFdlIGNvdWxkIHVzZSAkayQtZm9sZCBjcm9zcyB2YWxpZGF0aW9uIGluc3RlYWQsIGhvd2V2ZXIgc2V0dGluZyB0aGlzIHVwIHdpdGggdGhlIHByb3BlciBjb2RlIHdvdWxkIGJlIG11Y2ggbW9yZSBjb21wbGljYXRlZC4gV2hlbiBjb25kdWN0aW5nIGV4cGxvcmF0b3J5IGFuYWx5c2lzLCB5b3UgZG9uJ3QgbmVjZXNzYXJpbHkgbmVlZCB0byBkbyB0aGlzIG9uIHlvdXIgZmlyc3QgcGFzcyB0aHJvdWdoIHRoZSBkYXRhLiBDZXJ0YWlubHkgSSByZWNvbW1lbmQgdXNpbmcgQ1YgdG8gdmFsaWRhdGUgeW91ciBtb2RlbHMgYW5kIGNvbXBhcmUgdGhlbSBiZWZvcmUgcHVibGlzaGluZyBhbnl0aGluZywgYnV0IGZvciB0aGlzIGFwcGxpY2F0aW9uIEkgdGhpbmsgdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoIHdvcmtzIGZpbmUuXQoKYGBge3Igdm90ZTk2fQoobWggPC0gcmVhZF9jc3YoImRhdGEvbWVudGFsX2hlYWx0aC5jc3YiKSAlPiUKICBtdXRhdGVfZWFjaChmdW5zKGFzLmZhY3RvciguKSksIHZvdGU5NiwgYmxhY2ssIGZlbWFsZSwgbWFycmllZCkgJT4lCiAgbmEub21pdCkKCm1oX3NwbGl0IDwtIHJlc2FtcGxlX3BhcnRpdGlvbihtaCwgcCA9IGMoInRlc3QiID0gLjMsICJ0cmFpbiIgPSAuNykpCmBgYAoKIyMjIFNWTQoKTmV4dCBsZXQncyBjb21wYXJlIGEgZmV3IGRpZmZlcmVudCBTVk0gbW9kZWxzLiBBZ2FpbiB3ZSdsbCB1c2UgMTAtZm9sZCBDViBvbiB0aGUgdHJhaW5pbmcgc2V0IHRvIGRldGVybWluZSB0aGUgb3B0aW1hbCBjb3N0IHBhcmFtZXRlci4KCiMjIyMgTGluZWFyIGtlcm5lbAoKYGBge3Igdm90ZTk2LXN2bS1saW5lLCBkZXBlbmRzb249InZvdGU5NiJ9Cm1oX2xpbl90dW5lIDwtIHR1bmUoc3ZtLCB2b3RlOTYgfiAuLCBkYXRhID0gYXNfdGliYmxlKG1oX3NwbGl0JHRyYWluKSwKICAgICAgICAgICAgICAgICAgICBrZXJuZWwgPSAibGluZWFyIiwKICAgICAgICAgICAgICAgICAgICByYW5nZSA9IGxpc3QoY29zdCA9IGMoLjAwMSwgLjAxLCAuMSwgMSwgNSwgMTAsIDEwMCkpKQpzdW1tYXJ5KG1oX2xpbl90dW5lKQoKbWhfbGluIDwtIG1oX2xpbl90dW5lJGJlc3QubW9kZWwKc3VtbWFyeShtaF9saW4pCmZpdHRlZCA8LSBwcmVkaWN0KG1oX2xpbiwgYXNfdGliYmxlKG1oX3NwbGl0JHRlc3QpLCBkZWNpc2lvbi52YWx1ZXMgPSBUUlVFKSAlPiUKICBhdHRyaWJ1dGVzCgpyb2NfbGluZSA8LSByb2MoYXNfdGliYmxlKG1oX3NwbGl0JHRlc3QpJHZvdGU5NiwgZml0dGVkJGRlY2lzaW9uLnZhbHVlcykKcGxvdChyb2NfbGluZSkKYXVjKHJvY19saW5lKQpgYGAKCiMjIyBQb2x5bm9taWFsIGtlcm5lbAoKYGBge3Igdm90ZTk2LXN2bS1wb2x5LCBkZXBlbmRzb249InZvdGU5NiJ9Cm1oX3BvbHlfdHVuZSA8LSB0dW5lKHN2bSwgdm90ZTk2IH4gLiwgZGF0YSA9IGFzX3RpYmJsZShtaF9zcGxpdCR0cmFpbiksCiAgICAgICAgICAgICAgICAgICAga2VybmVsID0gInBvbHlub21pYWwiLAogICAgICAgICAgICAgICAgICAgIHJhbmdlID0gbGlzdChjb3N0ID0gYyguMDAxLCAuMDEsIC4xLCAxLCA1LCAxMCwgMTAwKSkpCnN1bW1hcnkobWhfcG9seV90dW5lKQoKbWhfcG9seSA8LSBtaF9wb2x5X3R1bmUkYmVzdC5tb2RlbApzdW1tYXJ5KG1oX3BvbHkpCmZpdHRlZCA8LSBwcmVkaWN0KG1oX3BvbHksIGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSwgZGVjaXNpb24udmFsdWVzID0gVFJVRSkgJT4lCiAgYXR0cmlidXRlcwoKcm9jX3BvbHkgPC0gcm9jKGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSR2b3RlOTYsIGZpdHRlZCRkZWNpc2lvbi52YWx1ZXMpCnBsb3Qocm9jX3BvbHkpCmF1Yyhyb2NfcG9seSkKYGBgCgojIyMgUmFkaWFsIGtlcm5lbAoKYGBge3Igdm90ZTk2LXN2bS1yYWQsIGRlcGVuZHNvbj0idm90ZTk2In0KbWhfcmFkX3R1bmUgPC0gdHVuZShzdm0sIHZvdGU5NiB+IC4sIGRhdGEgPSBhc190aWJibGUobWhfc3BsaXQkdHJhaW4pLAogICAgICAgICAgICAgICAgICAgIGtlcm5lbCA9ICJyYWRpYWwiLAogICAgICAgICAgICAgICAgICAgIHJhbmdlID0gbGlzdChjb3N0ID0gYyguMDAxLCAuMDEsIC4xLCAxLCA1LCAxMCwgMTAwKSkpCnN1bW1hcnkobWhfcmFkX3R1bmUpCgptaF9yYWQgPC0gbWhfcmFkX3R1bmUkYmVzdC5tb2RlbApzdW1tYXJ5KG1oX3JhZCkKZml0dGVkIDwtIHByZWRpY3QobWhfcmFkLCBhc190aWJibGUobWhfc3BsaXQkdGVzdCksIGRlY2lzaW9uLnZhbHVlcyA9IFRSVUUpICU+JQogIGF0dHJpYnV0ZXMKCnJvY19yYWQgPC0gcm9jKGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSR2b3RlOTYsIGZpdHRlZCRkZWNpc2lvbi52YWx1ZXMpCnBsb3Qocm9jX3JhZCkKYXVjKHJvY19yYWQpCmBgYAoKYGBge3IgbWgtcm9jLWNvbXBhcmUsIGRlcGVuZHNvbj1jKCJ2b3RlOTYtc3ZtLWxpbmUiLCJ2b3RlOTYtc3ZtLXBvbHkiLCJ2b3RlOTYtc3ZtLXJhZCIpfQpwbG90KHJvY19saW5lLCBwcmludC5hdWMgPSBUUlVFLCBjb2wgPSAiYmx1ZSIpCnBsb3Qocm9jX3BvbHksIHByaW50LmF1YyA9IFRSVUUsIGNvbCA9ICJyZWQiLCBwcmludC5hdWMueSA9IC40LCBhZGQgPSBUUlVFKQpwbG90KHJvY19yYWQsIHByaW50LmF1YyA9IFRSVUUsIGNvbCA9ICJvcmFuZ2UiLCBwcmludC5hdWMueSA9IC4zLCBhZGQgPSBUUlVFKQpgYGAKClNWTSBrZXJuZWwgfCBDViB0cmFpbmluZyBlcnJvciByYXRlCi0tLS0tLS0tLS0tfC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCkxpbmVhciAgICAgfCBgciBtaF9saW5fdHVuZSRiZXN0LnBlcmZvcm1hbmNlYApQb2x5bm9taWFsIHwgYHIgbWhfcG9seV90dW5lJGJlc3QucGVyZm9ybWFuY2VgClJhZGlhbCAgICAgfCBgciBtaF9yYWRfdHVuZSRiZXN0LnBlcmZvcm1hbmNlYAoKVGhpcyB0aW1lIHRoZSBTVk0gd2l0aCB0aGUgaGlnaGVzdCBBVUMgaXMgdGhlIGxpbmVhciBtb2RlbCwgZm9sbG93ZWQgYnkgdGhlIHJhZGlhbCBhbmQgdGhlbiB0aGUgcG9seW5vbWlhbCBTVk0uIEludGVyZXN0aW5nbHksIHRoZSBsaW5lYXIgU1ZNIGhhZCB0aGUgaGlnaGVzdCB0cmFpbmluZyBlcnJvciByYXRlIChjcm9zcy12YWxpZGF0ZWQpLCBmb2xsb3dlZCBieSByYWRpYWwsIGFuZCB0aGVuIHBvbHlub21pYWwgd2l0aCB0aGUgbG93ZXN0IGVycm9yIHJhdGUuIFRoZXNlIGFyZSBjcm9zcy12YWxpZGF0ZWQgbWVhc3VyZXMsIHNvIGl0J3Mgbm90IGFzIGlmIHRoZXkgc2hvdWxkIGJlIGhlYXZpbHkgYmlhc2VkLiBIb3dldmVyIHRoZXkgYXJlIGFsbCB3aXRoaW4gMSBwZXJjZW50YWdlIHBvaW50IG9mIGVhY2ggb3RoZXIsIHNvIHRoZSBkaWZmZXJlbmNlcyBtYXkgbm90IGFjdHVhbGx5IGJlIHRoYXQgc3Vic3RhbnRpYWwuIEZ1cnRoZXIgZXhwbG9yYXRpb24gY291bGQgYmUgd2FycmFudGVkIGhlcmUuCgpXZSBjb3VsZCB0aW5rZXIgd2l0aCB0aGUgcGFyYW1ldGVycyBmb3IgdGhlIHBvbHlub21pYWwgYW5kIHJhZGlhbCBrZXJuZWwgU1ZNcywgYWRqdXN0aW5nIHRoZSBudW1iZXIgb2YgZGVncmVlcyBpbiB0aGUgcG9seW5vbWlhbCBTVk0gYW5kIHRlc3RpbmcgZGlmZmVyZW50IGNvbnN0YW50cyAkXGdhbW1hJCBmb3IgdGhlIHJhZGlhbCBTVk0sIGFnYWluIHVzaW5nIDEwLWZvbGQgQ1YgdG8gc2VsZWN0IHRoZSBvcHRpbWFsIHZhbHVlcy4gSW5zdGVhZCB0aG91Z2gsIGxldCdzIHNlZSBob3cgdGhlIFNWTSB3aXRoIHRoZSBoaWdoZXN0IEFVQyAobGluZWFyKSBzdGFja3MgdXAgd2l0aCBzb21lIG9mIHRoZSBvdGhlciBzdGF0aXN0aWNhbCBsZWFybmluZyBtZXRob2RzIHdlIGNvdWxkIGFwcGx5LgoKIyMjIExvZ2lzdGljIHJlZ3Jlc3Npb24KCmBgYHtyIHZvdGU5Ni1sb2dpdH0KbWhfbG9naXQgPC0gZ2xtKHZvdGU5NiB+IC4sIGRhdGEgPSBhc190aWJibGUobWhfc3BsaXQkdHJhaW4pLCBmYW1pbHkgPSBiaW5vbWlhbCkKc3VtbWFyeShtaF9sb2dpdCkKCmZpdHRlZCA8LSBwcmVkaWN0KG1oX2xvZ2l0LCBhc190aWJibGUobWhfc3BsaXQkdGVzdCksIHR5cGUgPSAicmVzcG9uc2UiKQpsb2dpdF9lcnIgPC0gbWVhbihhc190aWJibGUobWhfc3BsaXQkdGVzdCkkdm90ZTk2ICE9IHJvdW5kKGZpdHRlZCkpCgpyb2NfbG9naXQgPC0gcm9jKGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSR2b3RlOTYsIGZpdHRlZCkKcGxvdChyb2NfbG9naXQpCmF1Yyhyb2NfbG9naXQpCmBgYAoKVGhlIHRlc3QgZXJyb3IgcmF0ZSBmb3IgdGhlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgaXMgYHIgbG9naXRfZXJyYC4KCiMjIyBEZWNpc2lvbiB0cmVlCgpgYGB7ciB2b3RlOTYtdHJlZX0KbWhfdHJlZSA8LSB0cmVlKHZvdGU5NiB+IC4sIGRhdGEgPSBhc190aWJibGUobWhfc3BsaXQkdHJhaW4pKQptaF90cmVlCgpwbG90KG1oX3RyZWUpCnRleHQobWhfdHJlZSwgcHJldHR5ID0gMCkKCmZpdHRlZCA8LSBwcmVkaWN0KG1oX3RyZWUsIGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSwgdHlwZSA9ICJjbGFzcyIpCnRyZWVfZXJyIDwtIG1lYW4oYXNfdGliYmxlKG1oX3NwbGl0JHRlc3QpJHZvdGU5NiAhPSBmaXR0ZWQpCgpyb2NfdHJlZSA8LSByb2MoYXMubnVtZXJpYyhhc190aWJibGUobWhfc3BsaXQkdGVzdCkkdm90ZTk2KSwgYXMubnVtZXJpYyhmaXR0ZWQpKQpwbG90KHJvY190cmVlKQphdWMocm9jX3RyZWUpCmBgYAoKVGhlIHRlc3QgZXJyb3IgcmF0ZSBmb3IgdGhlIGRlY2lzaW9uIHRyZWUgbW9kZWwgaXMgYHIgdHJlZV9lcnJgLgoKIyMjIEJhZ2dpbmcKCmBgYHtyIHZvdGU5Ni1iYWd9Cm1oX2JhZyA8LSByYW5kb21Gb3Jlc3Qodm90ZTk2IH4gLiwgZGF0YSA9IGFzX3RpYmJsZShtaF9zcGxpdCR0cmFpbiksCiAgICAgICAgICAgICAgICAgICAgICAgICBtdHJ5ID0gNykKbWhfYmFnCgp2YXJJbXBQbG90KG1oX2JhZykKCmZpdHRlZCA8LSBwcmVkaWN0KG1oX2JhZywgYXNfdGliYmxlKG1oX3NwbGl0JHRlc3QpLCB0eXBlID0gInByb2IiKVssMl0KCnJvY19iYWcgPC0gcm9jKGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSR2b3RlOTYsIGZpdHRlZCkKcGxvdChyb2NfYmFnKQphdWMocm9jX2JhZykKYGBgCgojIyMgUmFuZG9tIGZvcmVzdAoKYGBge3Igdm90ZTk2LXJmfQptaF9yZiA8LSByYW5kb21Gb3Jlc3Qodm90ZTk2IH4gLiwgZGF0YSA9IGFzX3RpYmJsZShtaF9zcGxpdCR0cmFpbikpCm1oX3JmCgp2YXJJbXBQbG90KG1oX3JmKQoKZml0dGVkIDwtIHByZWRpY3QobWhfcmYsIGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSwgdHlwZSA9ICJwcm9iIilbLDJdCgpyb2NfcmYgPC0gcm9jKGFzX3RpYmJsZShtaF9zcGxpdCR0ZXN0KSR2b3RlOTYsIGZpdHRlZCkKcGxvdChyb2NfcmYpCmF1Yyhyb2NfcmYpCmBgYAoKIyMjIENvbXBhcmUgdGhlIFJPQyBjdXJ2ZXMKCmBgYHtyIHZvdGU5Ni1jb21wYXJlLXJvY30KcGxvdChyb2NfcG9seSwgcHJpbnQuYXVjID0gVFJVRSwgY29sID0gImJsdWUiLCBwcmludC5hdWMueCA9IC4yKQpwbG90KHJvY19sb2dpdCwgcHJpbnQuYXVjID0gVFJVRSwgY29sID0gInJlZCIsIHByaW50LmF1Yy54ID0gLjIsIHByaW50LmF1Yy55ID0gLjQsIGFkZCA9IFRSVUUpCnBsb3Qocm9jX3RyZWUsIHByaW50LmF1YyA9IFRSVUUsIGNvbCA9ICJvcmFuZ2UiLCBwcmludC5hdWMueCA9IC4yLCBwcmludC5hdWMueSA9IC4zLCBhZGQgPSBUUlVFKQpwbG90KHJvY19iYWcsIHByaW50LmF1YyA9IFRSVUUsIGNvbCA9ICJncmVlbiIsIHByaW50LmF1Yy54ID0gLjIsIHByaW50LmF1Yy55ID0gLjIsIGFkZCA9IFRSVUUpCnBsb3Qocm9jX3JmLCBwcmludC5hdWMgPSBUUlVFLCBjb2wgPSAicHVycGxlIiwgcHJpbnQuYXVjLnggPSAuMiwgcHJpbnQuYXVjLnkgPSAuMSwgYWRkID0gVFJVRSkKYGBgCgoqIFNWTSAobGluZWFyIGtlcm5lbCkKKiBMb2dpc3RpYyByZWdyZXNzaW9uCiogRGVjaXNpb24gdHJlZQoqIEJhZ2dpbmcgKCRuID0gNTAwJCkKKiBSYW5kb20gZm9yZXN0ICgkbiA9IDUwMCwgbSA9IFxzcXJ0e3B9JCkKCkJhc2VkIHNvbGVseSBvbiB0aGUgdGVzdCBBVUMsIGxvZ2lzdGljIHJlZ3Jlc3Npb24gYW5kIHJhbmRvbSBmb3Jlc3QgcHJvdmlkZXMgdGhlIGhpZ2hlc3QgcHJlZGljdGl2ZSBhY2N1cmFjeSwgc2xpZ2h0bHkgYmV0dGVyIHRoYW4gdGhlIGxpbmVhciBrZXJuZWwgU1ZNLiBEZWNpc2lvbiB0cmVlIHBlcmZvcm1zIHRoZSB3b3JzdCwgdGhvdWdoIGFkbWl0dGVkbHkgQVVDIGlzIGJpYXNlZCBhZ2FpbnN0IGl0IHNpbmNlIGFsbCBkZWNpc2lvbiB0cmVlcyBwcm9kdWNlIGFyZSBwcmVkaWN0aW9ucywgbm90IHByb2JhYmlsaXRpZXMsIHNvIHRoZSBST0MgImN1cnZlIiBpcyBhY3R1YWxseSBhIHBvaW50LgoKIyBTZXNzaW9uIEluZm8gey50b2MtaWdub3JlfQoKYGBge3IgY2hpbGQ9J19zZXNzaW9uaW5mby5SbWQnfQpgYGAKCgoKCg==

This work is licensed under the CC BY-NC 4.0 Creative Commons License.